Submission #1369032

---

Source Code Expand

#include <bits/stdc++.h>
 
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long 
#define ld long double
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
 
#define y1 what
 
using namespace std;
 
const int N = (int) 2e5 + 10;
const int M = (int) 18;
const ll big =  (1LL << 51);
const ll LINF = (ll) 1e18;
const int INF = (int) 1e9 + 7;
const double EPS = (double) 1e-6;
const double PI =  3.14159265359;
 
int n, m, q;
int a[N], b[N], c[N], d[N];
vector<int> v[N], comp[N];
int was[N], clr[N];
int dist[5001][5001];
 
int main() {
    #define fn "balls"
    #ifdef witch
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
//        freopen(fn".in", "r", stdin);
//        freopen(fn".out", "w", stdout);
    #endif
    srand(time(0));
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dist[i][j] = INF;
        }
        dist[i][i] = 0;
        queue<int> q;
        q.push(i);
        while (!q.empty()) {
            int fr = q.front(); q.pop();
            for (auto it : v[fr]) {
                if (dist[i][fr] + 1 < dist[i][it]) {
                    dist[i][it] = dist[i][fr] + 1;
                    q.push(it);
                }
            }
        }
    }
    for (int i = n; i >= 1; i--) {
        d[i] = -INF;
    }
    for (int i = q; i >= 1; i--) {
        if (was[a[i]])
            continue;
        set<pii> q;
        q.insert(mp(-b[i], a[i]));
        d[a[i]] = b[i];
        was[a[i]] = c[i];
        clr[a[i]] = i;
        vector<int> all;
        while (!q.empty()) {
            int fr = q.begin() -> s;
            all.pb(fr);
            q.erase(q.begin());
            if (d[fr] == 0) 
                continue;
            for (auto it : v[fr]) {
                if (was[it]) {
                    if (clr[it] == i) 
                        continue;
                    //if (d[fr] - 2 * b[clr[it]] - 2 >= 0) {
                        for (auto go : comp[clr[it]]) {
                            //assert(!was[go]);
                            if (d[fr] - dist[it][go] - 2 > d[go]) {
                                was[go] = c[i];
                                clr[go] = i;
                                q.erase(mp(-d[go], go));    
                                d[go] = d[fr] - dist[it][go] - 2;  
                                q.insert(mp(-d[go], go));
                            }
                        }
                    //}
                } else {
                    if (d[fr] - 1 > d[it]) {
                        q.erase(mp(-d[it], it));
                        was[it] = c[i];
                        d[it] = d[fr] - 1;
                        clr[it] = i;
                        q.insert(mp(-d[it], it));
                    }
                }
            }
        }
        for (auto it : all) {
            for (auto add : v[it]) {
                if (!was[add])
                    comp[i].pb(add);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << was[i] << "\n";
    }
    return 0;
}

Submission Info

Judge Result