舞台装置の魔女 (AOJ 2318)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2318

問題

略

解法

解説参照。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n, m, T;
int dp[310];
vector<int> akuma[310]; // 自分自身がfromとなっているedgeのindexの集合
int edgeCount[1100];
int edgeTo[1100];
vector<int> edgeFrom[1100];

void Push(priority_queue<pair<int, int> > &que, int index) {
  int e = edgeFrom[index].size();
  vector<int> costs(e);
  REP(i, e) {
    costs[i] = dp[edgeFrom[index][i]];
  }
  sort(costs.rbegin(), costs.rend());
  int ans = 0;
  REP(i, e) {
    ans = max(ans, costs[i] + i);
  }
  que.push(make_pair(-ans, edgeTo[index]));
}

int main() {
  while (scanf("%d %d %d", &n, &m, &T) > 0) {
    // initialize
    T--;
    MEMSET(dp, -1);
    REP(i, 310) { akuma[i].clear(); }
    REP(i, 1100) { edgeFrom[i].clear(); }
    MEMSET(edgeCount, 0);
    MEMSET(edgeTo, -1);
    priority_queue<pair<int, int> > que;

    // input
    REP(i, n) {
      int leaf;
      int v = scanf("%d", &leaf);
      assert(v == 1);
      if (leaf == 1) {
        que.push(make_pair(-1, i));
      }
    }
    REP(i, m) {
      int k, to;
      int v = scanf("%d %d", &to, &k);
      assert(v == 2);
      to--;
      edgeTo[i] = to;
      edgeCount[i] = k;
      REP(j, k) {
        int from;
        int v = scanf("%d", &from);
        assert(v == 1);
        from--;
        edgeFrom[i].push_back(from);
        akuma[from].push_back(i);
      }
    }

    // process
    while (!que.empty()) {
      int node = que.top().second;
      int cost = -que.top().first;
      que.pop();
      if (dp[node] != -1) { continue; }
      dp[node] = cost;
      FORIT(it, akuma[node]) {
        edgeCount[*it]--;
        assert(edgeCount[*it] >= 0);
        if (edgeCount[*it] == 0) {
          Push(que, *it);
        }
      }
    }
    //REP(i, n) {
    //  cout << dp[i] << " ";
    //}
    //cout << endl;
    printf("%d\n", dp[T]);
  }
}