Submission #1195324

---

Source Code Expand

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;
int n, m, q;
vector<int> e[100005];
struct node {
    int v, d, c;
};
node t[100005];
void paint(node no)
{
    auto cur = no.v;
    // cout << cur << endl;
    if (t[cur].c != -1 && t[cur].d >= no.d) {
        return;
    } else if (t[cur].c != -1) {
        t[cur].d = no.d;
        if (no.d == 0)
            return;
        node ne{no.v, no.d - 1, no.c};
        for (auto to : e[cur]) {
            ne.v = to;
            paint(ne);
        }
    } else {
        t[cur] = no;
        if (no.d == 0)
            return;
        node ne{no.v, no.d - 1, no.c};
        for (auto to : e[cur]) {
            ne.v = to;
            paint(ne);
        }
    }
}
vector<node> query;
int main()
{
    cin >> n >> m;
    int a, b;
    int v, d, c;
    rep(i, m)
    {
        cin >> a >> b;
        a--, b--;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    cin >> q;
    node ini{0, 0, -1};
    rep(i, n)
    {
        ini.v = i;
        t[i] = ini;
    }
    rep(i, q)
    {
        cin >> v >> d >> c;
        v--;
        query.push_back({v, d, c});
    }
    reverse(query.begin(), query.end());
    rep(i, q)
    {
        paint(query[i]);
    }
    rep(i, n)
    {
        if (t[i].c == -1)
            t[i].c = 0;
        cout << t[i].c << endl;
    }
}

Submission Info

Judge Result