B - Splatter Painting

B - Splatter Painting

解法

後ろから見れば、頂点が塗られる回数は高々10^5なのでよさそう

dp[v][d] := vから周囲d以内が塗られている

とし、dp[v][d] からdp[t][d-1],dp[v][d-1]と伝播することで解ける

https://atcoder.jp/contests/agc012/submissions/4560743

undigraph<> g(2 * k5);
void solve() {
    cin >> n >> m;
    rep(i, m) {
        int f, t;
        cin >> f >> t;
        --f, --t;
        g.add(f, t);
    }
    cin >> q;
    vi v, d, co;
    na3(v, d, co, q);
    dec(v);
    vvi(was, k5, 14);
    vi res(n, 0);
    function<void(int, int, int)> rec = [&](int v, int d, int co) {
        if (d < 0)return;
        if (was[v][d])return;
        was[v][d] = 1;
        if (res[v] == 0)res[v] = co;
        rec(v, d - 1, co);
        forg(gi, g[v]) {
            rec(t, d - 1, co);
        }
    };
    rer(i, q - 1) {
        rec(v[i], d[i], co[i]);
    }
    rep(i, n)cout << res[i] << endl;
}