JOI - Spy を bitset でゴリ押す

問題リンク

JOI 2013 春合宿 2日目 3 - Spy

問題概要

• JOI 社と IOI 社の木が与えられる
• リーダーの配下の全社員が所属するグループが与えられる
• 2 つの木の対応する頂点について、共通して所属するグループを数える

想定解

JOI のページに載っている解説スライドによると、オイラーツアーと imos 法を使うのが想定解らしいです。

なんか面倒くさそうですね。(ちなみにそんなに面倒ではないです)

bitset 解法

ここからが本題です。

発想

社員 がプロジェクト に所属しているかどうかがわかれば楽勝です。 これは、最初にリーダーだけにこの情報を入れておき、それぞれのプロジェクトについて木上でimos法的なことをやれば、 でできます。

これは遅すぎるので、プロジェクトごとにしていた操作を一括でしたいです。

サイズ の bitset を 個用意してこの情報を管理すると、従来では個別にしていたimos法の処理を、bitwise or 演算一回で実現できます。

この超適当高速化により、何と TLE が取れてしまいます。bitset 最強 !!

ちなみに JOI 社と IOI 社の社員が共通して所属しているプロジェクトの数は、bitwise and で求められます。

実装

サイズ の bitset が 個必要なので、油断していると MLE します。気を付けましょう。

#include <bitset>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

constexpr int N = 2000;
constexpr int M = 500000;

int n, m;

int rootj, rooti;
vector<int> J[N], I[N];
bitset<M> joi[N], ioi[N];

queue<int> que;

int main() {

    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        if(a >= 0) J[a].push_back(i);
        else rootj = i;
        if(b >= 0) I[b].push_back(i);
        else rooti = i;
    }
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        joi[a - 1].set(i);
        ioi[b - 1].set(i);
    }

    que.push(rootj);
    while(!que.empty()) {
        int v = que.front();
        que.pop();
        for(int u : J[v]) {
            joi[u] |= joi[v];
            que.push(u);
        }
    }

    que.push(rooti);
    while(!que.empty()) {
        int v = que.front();
        que.pop();
        for(int u : I[v]) {
            ioi[u] |= ioi[v];
            que.push(u);
        }
    }

    for(int i = 0; i < n; i++)
        cout << (joi[i] & ioi[i]).count() << endl;

    return 0;
}