天下一プログラマーコンテスト2013 決勝: A - 天下一有無

https://beta.atcoder.jp/contests/tenka1-2013-final/tasks/tenka1_2013_final_a

問題概要

N×Mのグリッドの各マスに対して「着色されたマスが縦・横・斜めで隣り合わない」かつ「最低1マスは着色されている」という条件のもと色を塗るとき、何通りの塗り方があり得るか求めよ。

N, M <= 15

解法

上の行から順に各マスを塗る・塗らないのbitDPをしていく。遷移を単純にやると215×215かかってしまうが、そもそも215の中には正しくない塗り方(塗りが隣り合う)がかなりの数含まれているため、そういうのを飛ばす枝刈りを入れると十分間に合う(M=15のとき正しい塗り方は1597通りしかない)。

感想

Aなのにむずいしどこにも解説ないし辛かった

指数時間アルゴリズムは枝刈りが本質になり得るという学びがあった(これが想定解なのかわからんが)

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable long MOD = 10^^9 + 7;

bool valid(int mask) {
    return !((mask & (mask << 1)) || (mask & (mask >> 1)));
}

bool valid2(int mask1, int mask2) {
    return !((mask1 & (mask2 << 1)) || (mask1 & mask2) || (mask1 & (mask2 >> 1)));
}

void main() {
    auto s = readln.split.map!(to!int);
    auto H = s[0];
    auto W = s[1];
    auto masks = iota(1<<W).filter!(a => valid(a)).array;

    auto dp = new long[][](H+1, 1<<W);
    dp[0][0] = 1;

    foreach (r; 0..H) {
        foreach (mask1; masks) {
            if (dp[r][mask1] == 0) continue;
            foreach (mask2; masks) {
                if (!valid2(mask1, mask2)) continue;
                dp[r+1][mask2] += dp[r][mask1];
                dp[r+1][mask2] %= MOD;
            }
        }
    }

    auto ans = (dp[H].sum - 1) % MOD;
    ans.writeln;
}

天下一プログラマーコンテスト2016予選B: D - 天下一数列にクエリを投げます

https://beta.atcoder.jp/contests/tenka1-2016-qualb/tasks/tenka1_2016_qualB_d

問題概要

N要素の数列a1, a2, .., aNに対してA個の加算クエリとB個の調査クエリが与えられるので順次処理せよ。

  • 加算クエリ: 数列の区間[L, R]にXを加算する
  • 調査クエリ: S回目の加算クエリを実行する直前からT回目の加算クエリを実行した直後までで、数列のK番目がとる値の最小値

N, A, B <= 105

解法

「ある時点での数列の各要素の値」を追いかけたくなるが、そうではなく「数列のある要素の全ての時点での値」に注目するとうまくいく。イメージとしては以下のような処理の流れになる。まず(加算クエリの数)要素ある数列を用意し、これを各加算クエリ実行時点でのa1の値とみなす。次に左端が1であるような加算クエリを持ってくる。このクエリの順番をt, 足される値をxとすると、t回目のクエリ以後はa1の値はx足されていることになるわけなので、用意した数列のt番目以降の要素に一律xを加算する。次にa1が対象の調査クエリを持ってきて、区間[S-1, T]をチェックすればこの調査クエリの答えが求まる。ここまで処理が終わったら今度はこの数列をa2のものと見なすことにする。このとき区間[L, R]のRがa1であるような加算クエリの分は消す必要があるので、先ほどの加算の逆操作(t番目以降に一律-xを足す)を行う。以上を繰り返していけばすべてのクエリを処理していくことができる。そしてここで必要となっている区間加算、区間最小取得といった処理は遅延評価セグメントツリーを用いれば効率的に行うことができ、時間内に答えを出すことができる。

感想

言われてみれば…というタイプの問題だけど自分で思いつくのは厳しかった

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

alias Tuple!(int, "t", int, "l", int, "r", int, "x") Query;

void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!long).array;
    auto q1 = readln.chomp.to!int;
    auto Q1 = q1.iota.map!(i => (i+1) ~ readln.split.map!(to!int).array).array;
    auto q2 = readln.chomp.to!int;
    auto Q2 = q2.iota.map!(i => (i+1) ~ readln.split.map!(to!int).array).array;
    auto st = new LazySegmentTree!long(q1+10);
    auto ans = new long[](q2);

    auto add_queue1 = new BinaryHeap!(Array!Query, "a.l > b.l");
    auto add_queue2 = new BinaryHeap!(Array!Query, "a.r > b.r");
    foreach (q; Q1) add_queue1.insert(Query(q[0], q[1], q[2], q[3]));
    Q2.sort!"a[3] < b[3]";
    int p = 0;

    foreach (i; 1..N+1) {
        while (!add_queue2.empty && add_queue2.front.r < i) {
            auto q = add_queue2.front;
            add_queue2.removeFront;
            st.add(q.t, q1+1, -q.x);
        }
        while (!add_queue1.empty && add_queue1.front.l == i) {
            auto q = add_queue1.front;
            add_queue1.removeFront;
            st.add(q.t, q1+1, q.x);
            add_queue2.insert(q);
        }
        while (p < q2 && Q2[p][3] == i) {
            ans[Q2[p][0]-1] = st.getVal(Q2[p][1]-1, Q2[p][2]) + A[i-1];
            ++p;
        }
    }

    ans.each!writeln;
}

class LazySegmentTree(T) {
    T[] table;
    T[] lazy_;
    int size;

    this(int n) {
        assert(bsr(n) < 29);
        size = 1 << (bsr(n) + 2);
        table = new T[](size);
        lazy_ = new T[](size);
        fill(table, 0);
        fill(lazy_, 0);
    }

    void eval(int i, int l, int r) {
        if (lazy_[i] == 0) return;

        table[i] += lazy_[i];
        if (l != r) {
            lazy_[i*2+1] += lazy_[i];
            lazy_[i*2+2] += lazy_[i];
        }

        lazy_[i] = 0;
    }

    void add(int a, int b, T num) {
        add(a, b, num, 0, 0, size/2-1);
    }

    void add(int a, int b, T num, int i, int l, int r) {
        eval(i, l, r);

        if (a > r || b < l) return;
        if (a <= l && r <= b) {
            lazy_[i] += num;
            eval(i, l, r);
        } else {
            add(a, b, num, i*2+1, l, (l+r)/2);
            add(a, b, num, i*2+2, (l+r)/2+1, r);
            table[i] = min(table[i*2+1], table[i*2+2]);
        }
    }

    T getVal(int a, int b) {
        return getVal(a, b, 0, 0, size/2-1);
    }

    T getVal(int a, int b, int i, int l, int r) {
        eval(i, l, r);

        if (a > r || b < l) return 1L << 59;
        if (a <= l && r <= b) return table[i];
        return
            min(getVal(a, b, i*2+1, l, (l+r)/2),
                getVal(a, b, i*2+2, (l+r)/2+1, r));
    }
}

SoundHound Programming Contest 2018 Masters Tournament 本戦: E - Hash Swapping

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_e

問題概要

長さNの文字列がM個与えられる。それらに対するQ個のクエリを順次処理せよ。

  • swapクエリ: x番目の文字列とy番目の文字列の、l番目からr番目の文字を入れ替える
  • hashクエリ: x番目の文字列のハッシュ値(問題文参照)を求めて出力する

N, Q <= 2*105

M <= 20

解法

TL長めなので平方分割でできる。平方分割に関しては前も同じことを書いたが↓の記事を見るのが一番わかりやすいと思う。

なお上の記事だと値をまとめる用のbucketSumと1個1個の値を持っておく用のdataをそれぞれ1個の配列で持っているが、この問題だとswap操作が若干めんどくさいので、bucketSumとdataをそれぞれ区間ごとに細切れにして持っておくみたいなことをしたら実装がある程度簡単になった。

感想

本番平方分割したらいいんじゃねまでは行ったけど全然時間足りず。落ち着いて書き直したら自分の中で平方分割の実装がなんとなく整理ついてきたので次回以降は何卒

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable long MOD = 10^^9 + 7;
immutable long BASE = 10^^6;
immutable int SIZE = 450;
long BUCKET_BASE;

class Node {
    long big;
    long[] small;

    this(string s) {
        small = new long[](SIZE);
        foreach (i; 0..s.length) {
            small[i] = s[i] - 'a' + 1;
        }
        hash;
    }

    void hash() {
        big = 0;
        foreach_reverse (i; 0..SIZE) {
            big = big * BASE % MOD;
            big = (big + small[i]) % MOD;
        }
    }
}


long calc(const Node[] str, int l, int r) {
    long ret = 0;
    foreach_reverse (i; l/SIZE..(r-1)/SIZE+1) {
        int bl = i * SIZE;
        int br = i * SIZE + SIZE;
        if (l > bl || r < br) {
            foreach_reverse (j; max(l, bl)..min(r, br)) {
                ret = ret * BASE % MOD;
                ret = (ret + str[i].small[j%SIZE]) % MOD;
            }
        } else {
            ret = ret * BUCKET_BASE % MOD;
            ret = (ret + str[i].big) % MOD;
        }
    }
    return ret;
}

void nswap(Node[] x, Node[] y, int l, int r) {
    foreach (i; l/SIZE..(r-1)/SIZE+1) {
        int bl = i * SIZE;
        int br = i * SIZE + SIZE;
        if (l > bl || r < br) {
            foreach (j; max(l, bl)..min(r, br)) {
                swap(x[i].small[j%SIZE], y[i].small[j%SIZE]);
            }
            x[i].hash;
            y[i].hash;
        } else {
            swap(x[i].big, y[i].big);
            swap(x[i].small, y[i].small);
        }
    }
}

long powmod(long a, long x, long m) {
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}

void main() {
    BUCKET_BASE = powmod(BASE, SIZE, MOD);
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto S = M.iota.map!(_ => readln.chomp).array;
    
    auto strs = new Node[][](M, SIZE);
    foreach (i; 0..M) 
        foreach (j; 0..SIZE) 
            if (j*SIZE < N) 
                strs[i][j] = new Node(S[i][j*SIZE..min(N, j*SIZE+SIZE)]);
    
    auto Q = readln.chomp.to!int;
    
    while (Q--) {
        auto q = readln.split.map!(to!int);
        int type = q[0];
        int x = q[1] - 1;
        int y = q[2] - 1;
        int l = q[3] - 1;
        int r = q[4];
        
        if (type == 1) {
            nswap(strs[x], strs[y], l, r);
        } else {
            calc(strs[x], l, r).writeln;
        }
    }
}

SoundHound Programming Contest 2018 Masters Tournament 本戦: D - Propagating Edges

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_d

問題概要

N頂点0辺の無向グラフに対してQ個のクエリが飛んでくるので順次処理せよ。

  • addクエリ: 頂点u, v間に辺を張る
  • completeクエリ: 「頂点u」と「頂点uと連結な頂点」の集合に含まれるすべての頂点間に辺を張る
  • checkクエリ: 頂点u, v間に辺が張られているかどうかを答える

N <= 105

Q <= 2*105

解法

2頂点間に辺が張られるのは当然ながらaddクエリかcompleteクエリのどちらかの影響である。このうちaddクエリの結果張られた辺は全部覚えておくことができる。一方でcompleteクエリは愚直にやると時間も空間もO(N2)かかってしまうのでここをなんとかする必要がある。結論からいうとcompleteクエリは頂点の縮約操作と見なすことで効率的に処理することができる。具体的にはaddクエリによって追加された辺に基づいて普通にグラフを構築しておき、completeクエリが来たら頂点uと連結な頂点をDFSで列挙してひとつの頂点にまとめてしまう。まとめる操作はUnionFindで実現できる。こうしておくと頂点u, v間に辺が張られているのは 「addクエリの記録にu, vがある」もしくは「uとvがUnionFindで同じ集合にまとめられている」ときのみであるから、checkクエリの際にはこれだけチェックすればよい。以降のaddクエリ、completeクエリは縮約後の頂点に読み替えて操作を行えばよい(ただし「addクエリの直接的な記録」は元の頂点で持っておく)。縮約操作は1つの頂点につきたかだか1回しか行われないので、計算量は増えない。

感想

すいません本番で通したんですが完全に嘘解法でした 自分で一瞬で撃墜してしまった

改めてちゃんとした解法を見てやったらUnionFindで管理してるのが連結頂点の集合ではなくcompleteになった集合というところで頭がこんがらがって大変だった

コード

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto Q = s[1];
    
    auto uf = new UnionFind(N);
    auto added = new bool[int][](N);
    auto G = new bool[int][](N);
    bool[int] used;

    void dfs(int n) {
        if (n in used) return;
        used[n] = true;
        foreach (m; G[n].keys) {
            if (m in used) continue;
            dfs(m);
        }
    }

    while (Q--) {
        auto q = readln.split.map!(to!int);
        int type = q[0];
        int u = q[1] - 1;
        int v = q[2] - 1;
        int up = uf.find(u);
        int vp = v >= 0 ? uf.find(v) : 0;
        if (type == 1) {
            added[u][v] = true;
            added[v][u] = true;
            G[up][vp] = true;
            G[vp][up] = true;
        } else if (type == 2) {
            auto hoge = used.keys.dup;
            foreach (h; hoge) used.remove(h);
            dfs(up);
            foreach (k; used.keys) {
                uf.unite(up, k);
                hoge = G[k].keys.dup;
                foreach (h; hoge) G[k].remove(h);
            }
        } else {
            if (v in added[u] || up == vp) {
                writeln("Yes");
            } else {
                writeln("No");
            }
        }
    }
}

class UnionFind {
    int N;
    int[] table;

    this(int n) {
        N = n;
        table = new int[](N);
        fill(table, -1);
    }

    int find(int x) {
        return table[x] < 0 ? x : find(table[x]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (table[x] > table[y]) swap(x, y);
        table[x] += table[y];
        table[y] = x;
    }
}

SoundHound Programming Contest 2018 Masters Tournament 本戦: C - Not Too Close

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_c

問題概要

N頂点の無向グラフで、頂点に1からNまでの番号がついており、自己辺・多重辺を持たず、すべての辺の長さを1としたとき頂点1-2間の最短距離がDであるようなものが何通りあるか求めよ。

D < N <= 30

解法

頂点1を基準として、「頂点1から距離1の頂点」「距離2の頂点」...という風にどんどん頂点をくっつけてグラフを構成していくことを考える。この数え上げは以下のDPで行える。

dp(i, j, k): 距離iまで構成し、j個の頂点を使い、最後にくっつけた距離iの頂点の数がk個であるグラフの数

距離dの頂点を追加するときは、以下のことを考慮に入れる。

  1. 何個の頂点を距離dとしてくっつけるか
  2. 頂点の選び方は何通りあるか
  3. 辺の張り方は何通りあるか

頂点の選び方は(未使用頂点の数)から(使用頂点の数)を選ぶ組合せなのでコンビネーションで計算できる。ただし頂点2の扱いに注意が必要で、距離がDではないときに頂点2を選んではいけないし、候補にも入れてはいけない。逆に距離がDの時は頂点2は必ず選ぶ。この点で上の組合せの計算には微妙に足し引きが入る。

辺の張り方に関しては以下のことを考慮に入れる → 距離(d-1)の頂点のうち少なくともひとつには辺を張らなければならない。距離(d-2)以下の頂点には辺を張ってはならない。また距離dの頂点同士は好きなだけ辺を張れる。

最後に作ったグラフのうち余った頂点がある場合、その余った頂点同士でいくらでも辺が張れるという点に留意する。

状態数がO(N3), 遷移がO(N)(何個頂点をくっつけるかの列挙)なのでO(N4). Nが小さいのでこれで十分間に合う。

感想

解説聞いたうえで実装し始めたけど最後の余った頂点のところを見落としててドツボに入ってしまった。考え方自体は確かにどこかで見たことあるといえる感じなのでちゃんとできるようになっておきたい

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable long MOD = 10^^9 + 7;
long[] F;
long[] G;

void main() {
    F = new long[](50);
    G = new long[](50);
    F[0] = F[1] = 1;
    foreach (i; 2..50) F[i] = F[i-1] * i % MOD;
    foreach (i; 0..50) G[i] = powmod(F[i], MOD-2, MOD);

    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto D = s[1];

    auto dp = new long[][][](N, N+1, N+1);
    dp[0][1][1] = 1;

    foreach (d; 1..N) {
        foreach (using; 1..N+1) {
            foreach (used; 1..N+1) {
                if (using + used > N) continue;
                foreach (last; 1..N+1) {
                    long rest = d <= D ? N - used - 1 : N - used;
                    long k = d == D ? using - 1 : using;
                    if (rest < k) continue;
                    long tmp = comb(rest, k);
                    tmp = tmp * powmod(powmod(2, last, MOD) - 1, using, MOD) % MOD;
                    tmp = tmp * powmod(2, using * (using - 1) / 2, MOD) % MOD;
                    (dp[d][using+used][using] += dp[d-1][used][last] * tmp % MOD) %= MOD;
                }
            }
        }
    }

    long ans = 0;
    foreach (d; D..N)
        foreach (n; d+1..N+1)
            foreach (last; 0..N+1) {
                long tmp = dp[d][n][last];
                tmp = tmp * powmod(2, (N-n)*(N-n-1)/2, MOD) % MOD;
                ans = (ans + tmp) % MOD;
            }
    ans.writeln;
}

long powmod(long a, long x, long m) {
    a %= m;
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}

long comb(long n, long k) {
    return F[n] * G[n-k] % MOD * G[k] % MOD;
}

SoundHound Programming Contest 2018 Masters Tournament 本戦: B - Neutralize

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_b

問題概要

N要素の数列Aが与えられる。Aの中から連続するK個の要素を選んでその値を全て0にするという操作を何度でも行えるとき、最終的なAの全要素の和の最大値を求めよ。

N <= 2×105

-109 <= Aの要素 <= 109

解法

まず「連続するK個を選んで」は「連続するK個以上を選んで」と言い換えられる。一度K個連続で潰したあとひとつずらしてまた潰せば(K+1)個連続で0にできるからである。

また操作の順番は最終的な結果に影響を及ぼさないので、左の要素から順に操作を行うかどうか決めていってよい。もしその要素を残すのであれば合計にその要素の値を組み入れて次の要素へ進む、潰すのであれば合計はいじらずK個以上先の要素へスキップする、という感じ。

ここまでを踏まえるとDPできそうな感じになる。K個以上先へのスキップという遷移を愚直にやるとO(N2)かかるのでNGだが、「直前でスキップした結果今見ている要素にたどりついたのであれば、1つ飛ばしのスキップが可能」(さっきの潰した区間をさらに1伸ばすイメージ)という風にみなせば「残して1個進む」「K個スキップする」「直前でスキップしてるので今の要素をスキップして1個進む」の3種類の遷移だけ考えればよくなるので(インデックス、直前にスキップしたか)を状態にとるDPができてO(N)になる。

感想

DPにたどり着くまで時間がかかって全然解けなかったのでかなり焦った

遷移は変な工夫しないでも遅延セグ木とかでできそう もらうDPなら普通のセグ木でもいける?

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable long INF = 1L << 59;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto K = s[1];
    auto A = N.iota.map!(_ => readln.chomp.to!long).array;
    auto B = new long[](N+1);
    foreach (i; 0..N) B[i+1] = B[i] + A[i];

    auto dp = new long[][](N+1, 2);
    foreach (i; 0..N+1) fill(dp[i], -INF);
    dp[0][0] = 0;

    foreach (i; 0..N) {
        dp[i+1][0] = max(dp[i+1][0], max(dp[i][0], dp[i][1]) + A[i]);
        dp[i+1][1] = max(dp[i+1][1], dp[i][1]);
        if (i+K <= N)
            dp[i+K][1] = max(dp[i+K][1], dp[i].reduce!max);
    }

    max(dp[N][0], dp[N][1], 0).writeln;
}

Codeforces Round #499 (Div. 1): D. Mars rover

http://codeforces.com/contest/1010/problem/D

問題概要

N頂点の根付き木が与えられる。すべての葉にはあらかじめ1か0の入力が与えられており、葉以外の頂点はすべて「子から来たビットを入力として論理演算をし、その出力を親に送る」機能を持っている。演算の種類はNOT, AND, OR, XORであり、NOTの頂点はひとつの子、それ以外は2つの子を持つ。すべての葉について、その葉の入力のみ反転させたとき、最終的に根が出力するビットが何になるかを求めよ。

N <= 106

解法

まずあらかじめ与えられた入力での計算結果がどうなるかは事前にO(N)で計算できる。その上でまた根から順に「もし子が送ってくる出力が反転したら、この頂点の出力も反転するか」を求めていく。例えばANDの頂点で両方の子がともに0ならば、どちらかの子が反転したところで結局出力は0になる(=その下の葉で入力が何になろうと最終的な答えは変わらない)。一方で左の子が1, 右の子が0だった場合、右の子が反転するとANDの出力も0から1に反転する。よって右の子の反転は最終的な結果も反転させうる(もちろんそれより上の頂点で反転が無意味になってたら駄目)。という感じで場合分けしてDFSしていくと最終的にそれぞれの葉で反転が有効か無効かがわかる。有効なら最初に求めた根の出力を反転させればいいし、そうでないならそのままの出力を使えばいい。

感想

まったく見当違いなことをしていた(NOTは縮約できるじゃん→そしたら2分木になるから高さlogNじゃん→は?)

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

void main() {
    enum OP {IN, NOT, AND, OR, XOR};
    auto N = readln.chomp.to!int;
    auto G = new int[][](N, 2);
    auto P = new int[](N);
    auto B = new bool[](N);
    auto V = new bool[](N);
    auto ops = new OP[](N);

    foreach (i; 0..N) {
        auto s = readln.split;
        string op = s[0];
        foreach (j; 1..s.length) {
            int a = s[j].to!int - 1;
            G[i][j-1] = a;
            if (op != "IN")
                P[a] = i;
        }
        
        if (op == "IN") {
            ops[i] = OP.IN;
            B[i] = s[1] == "1";
        } else if (op == "NOT") {
            ops[i] = OP.NOT;
        } else if (op == "AND") {
            ops[i] = OP.AND;
        } else if (op == "OR") {
            ops[i] = OP.OR;
        } else {
            ops[i] = OP.XOR;
        }
    }

    bool operate(int n) {
        bool a = G[n][0] >= 0 ? B[G[n][0]] : 0;
        bool b = G[n][1] >= 0 ? B[G[n][1]] : 0;
        if (ops[n] == OP.IN) {
            return B[n];
        } else if (ops[n] == OP.NOT) {
            return !a;
        } else if (ops[n] == OP.AND) {
            return a & b;
        } else if (ops[n] == OP.OR) {
            return a | b;
        } else if (ops[n] == OP.XOR) {
            return a ^ b;
        }
        return 0;
    }

    void init(int n) {
        if (ops[n] == OP.IN) {
            return;
        } else if (ops[n] == OP.NOT) {
            int a = G[n][0];
            init(a);
        } else {
            int a = G[n][0];
            int b = G[n][1];
            init(a);
            init(b);
        }
        B[n] = operate(n);
    }

    void dfs(int n, bool valid) {
        V[n] = valid;
        int a = G[n][0];
        int b = G[n][1];
        if (ops[n] == OP.NOT) {
            dfs(a, valid);
        } else if (ops[n] == OP.AND) {
            if (B[a] && B[b]) {
                dfs(a, valid);
                dfs(b, valid);
            } else if (B[a] && !B[b]) {
                dfs(a, false);
                dfs(b, valid);
            } else if (!B[a] && B[b]) {
                dfs(a, valid);
                dfs(b, false);
            } else {
                dfs(a, false);
                dfs(b, false);
            }
        } else if (ops[n] == OP.OR) {
            if (B[a] && B[b]) {
                dfs(a, false);
                dfs(b, false);
            } else if (B[a] && !B[b]) {
                dfs(a, valid);
                dfs(b, false);
            } else if (!B[a] && B[b]) {
                dfs(a, false);
                dfs(b, valid);
            } else {
                dfs(a, valid);
                dfs(b, valid);
            }
        } else if (ops[n] == OP.XOR) {
            dfs(a, valid);
            dfs(b, valid);
        }
    }

    init(0);
    dfs(0, true);
    N.iota.filter!(i => ops[i] == OP.IN).map!(i => V[i] ? !B[0] : B[0]).map!(i => i.to!int.to!string).join("").writeln;
}