AtCoder Grand Contest 012: B - Splatter Painting

,

http://agc012.contest.atcoder.jp/tasks/agc012_b

solution

クエリを後ろから処理し積極的に枝刈りする。$D = \max d_i \le 10$の制約から$O(Q + (N + M) D)$で間に合う。

それぞれの頂点で、その頂点$v$から距離$d$以内の頂点が全て塗られているような値$d_v$を(保守的に)持たせておく。 これはその頂点に(直接あるいは間接的に)来たクエリの値を覚えておくだけ。 後ろから処理していくので、覚えている距離$d_v$よりクエリの値$d_i$が小さいならその場で打ち切れる。 打ち切られずに処理が走るのは高々$\max d_i$回だけなので、これは計算量を落とす。

implementation

#include <cstdio>
#include <queue>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;

int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<vector<int> > g(n);
    repeat (i, m) {
        int a, b; scanf("%d%d", &a, &b); -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int q; scanf("%d", &q);
    vector<int> v(q), d(q), c(q); repeat (t, q) { scanf("%d%d%d", &v[t], &d[t], &c[t]); -- v[t]; }
    // solve
    vector<int> result(n);
    vector<int> used(n, -1);
    repeat_reverse (t, q) {
        queue<int> que;
        auto push = [&](int i, int dist) {
            if (used[i] < dist) {
                used[i] = dist;
                if (not result[i]) result[i] = c[t];
                que.emplace(i);
            }
        };
        push(v[t], d[t]);
        while (not que.empty()) {
            int i = que.front(); que.pop();
            if (used[i] != 0) {
                for (int j : g[i]) {
                    push(j, used[i]-1);
                }
            }
        }
    }
    // output
    repeat (i, n) {
        printf("%d\n", result[i]);
    }
    return 0;
}