JOI2013春合宿Day2 スパイ(Spy)

問題

http://www.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day2.pdf
割愛(必要ない気がしてきた)

解法

プロジェクトがいっぱい与えられてつらいので、とりあえずIOI社のプロジェクトリーダーとなった人々にプロジェクトの内容をpush_backしておきます。
そして複数のプロジェクトを1人の社員で一度に処理してしまうことを考えます。
IOI社の社長(根)から各社員(頂点)へ深さ優先探索で訪れます。
訪れたときにその社員がリーダーとなっているプロジェクトを追加して帰るときには削除する、という感じでプロジェクトを持ちながら探索すれば、常に今の社員から見るべきプロジェクトだけがわかります。
あとは、今の社員に対応したJOI社側の社員が、それらのプロジェクトのうちいくつに属しているかを知りたいですね。
それを知るために、累積和を使います。
累積和用の配列を用意し、プロジェクトを追加するときに、JOI社側のそのプロジェクトリーダーのところに+1しておきます。
逆に、もう見なくてよくなったプロジェクトに対しては、そのJOI社側のリーダーのところから-1してなかったことにします。
これらはです。
そのようにしておけば、調べたいJOI社の社員から根に向かって登りながら累積和を取るだけで、その社員が今見ているプロジェクトのうちいくつに属しているかを知ることができます。
これはです。
深さ優先探索でN個の各頂点に訪れてからこの判定を行うので、全体ではです。

(補足)
想定解法の解説を見ました。美しいですね...
ほかにも解き方があるらしいです。

コード

using namespace std;

int N, M, P[2000], Q[2000], R[500000], S[500000];
int sum[2000], ans[2000];
vector<int> ie[2000], project[2000];

int Count(int v)
{
    int res = 0;
    while (v != -1)
    {
        res += sum[v];
        v = Q[v];
    }
    return res;
}

void DFS(int v)
{
    for (int i = 0; i < project[v].size(); i++)
    {
        sum[project[v][i]]++;
    }
    ans[v] = Count(v);
    for (int i = 0; i < ie[v].size(); i++)
    {
        DFS(ie[v][i]);
    }
    for (int i = 0; i < project[v].size(); i++)
    {
        sum[project[v][i]]--;
    }
}

int main()
{
    cin >> N >> M;
    int root;
    for (int i = 0; i < N; i++)
    {
        cin >> P[i] >> Q[i];
        P[i]--; Q[i]--;
        if (P[i] < 0)
        {
            root = i;
            continue;
        }
        ie[P[i]].push_back(i);
    }
    for (int i = 0; i < M; i++)
    {
        cin >> R[i] >> S[i];
        R[i]--; S[i]--;
        project[R[i]].push_back(S[i]);
    }
    DFS(root);
    for (int i = 0; i < N; i++)
    {
        printf("%d\n", ans[i]);
    }
    return 0;
}