はまやんはまやんはまやん

hamayanhamayan's blog

SNS のログ / Restore [第一回 アルゴリズム実技検定 過去問 E]

https://atcoder.jp/contests/past201912-open/tasks/past201912_e

解説

https://atcoder.jp/contests/past201912-open/submissions/9252782

実装が厳しくなってくる。
N≦100なので、計算量は雑にやっても問題ない。
follow[i][j] := iがjをフォローしているか
これを持っておこう。
これはboolの2次元配列で持つのではなく、bitsetの1次元配列として持っておくと実装が少し楽になる。

フォロー操作
follow[a][b] = trueとするだけ

フォロー全返し
ユーザーu全てに対して、follow[u][a]=trueであればfollow[a][u]をtrueにする

フォローフォロー
ユーザーu全てに対して、follow[a][u]=trueであれば、follow[a] |= follow[u]とする。
これはbitsetで保持しているからできる芸当であるが、
boolの2次元配列でもループを1つ増やせば同等の操作ができる。

あとは、followを見ながら答える。
操作の過程で自分をfollowしてしまう可能性があるので、それをNにするのを忘れなく。
あと、順番に更新していくと、更新した情報を使って更に更新みたいなことをしてしまう場合があるので、注意。

int N, Q;
bitset<100> follow[100];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(q, 0, Q) {
        int t; cin >> t;
        if (t == 1) {
            int a, b; cin >> a >> b; a--; b--;
            follow[a][b] = true;
        }
        else if (t == 2) {
            int a; cin >> a; a--;
            rep(u, 0, N) if (follow[u][a]) follow[a][u] = true;
        }
        else {
            int a; cin >> a; a--;
            vector<int> follow_user;
            rep(x, 0, N) if (follow[a][x]) follow_user.push_back(x);
            fore(x, follow_user) follow[a] |= follow[x];
        }
    }
    rep(i, 0, N) follow[i][i] = false;

    rep(i, 0, N) {
        rep(j, 0, N) {
            if(follow[i][j]) printf("Y");
            else printf("N");
        }
        printf("\n");
    }
}