AGC012 B - Splatter Painting

　問題

N個の頂点とM個の辺のグラフが与えられる。最初、頂点は全て色0で塗られている。 それぞれの辺の長さは1である。 さらに、Q個の操作が与えられる。各操作は vi, di, ciという形式で与えられる。この意味は、頂点viから距離di以内にある頂点を色ciで上書きするということ。

方針

Q個の操作をそのままの順番で実行すると、計算量がO(N²)となり間に合わない。 Q個の操作を逆順に行う事を考える。逆順にすると、その操作によって塗られた頂点は二度と上書きされない。 dp[v][d]をつくり、同じ(v, d)について再び計算をしないようにすると（メモ化）、計算量はO(Q+(N+M)*max(di))となるらしい。

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;

vector<int> g[100010];
vector<int> color(100010, 0);
vector< vector<bool> > dp;

void search(int d, int v, int c) {
    if(dp[v][d]) return;
    dp[v][d] = true;
    if(color[v]==0) color[v] = c;
    if(d==0) {
        //color[v] = c; 
        return;
    }
    search(d-1, v, c);
    for(int i=0;i<g[v].size();i++) {
        search(d-1, g[v][i], c);
    }

}

int main() {
    dp = vector< vector<bool> >(100010, vector<bool>(12, false));
    ll n, m;
    cin >> n >> m;
    for(int i=0;i<m;i++) {
        int ai, bi;
        cin >> ai >> bi;
        ai--; bi--;
        g[ai].push_back(bi);
        g[bi].push_back(ai);
    }
    int Q;
    cin >> Q;
    vector<int> v(Q), dv(Q), cv(Q);
    for(int i=0;i<Q;i++) {
        cin >> v[i] >> dv[i] >> cv[i];
        v[i]--;
    }

    for(int i=Q-1;i>=0;i--) {
        search(dv[i], v[i], cv[i]);
    }

    for(int i=0;i<n;i++) {
        cout << color[i] << endl;
    }

}