Submission #1195361

---

Source Code Expand

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
#include <deque>
#include <stack>
#include <stdio.h>
#include <map>
#include <set>
#include <time.h>
#include <string>
#include <fstream>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <assert.h>
#include <list>
#include <unordered_map>
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define pdd pair<double,double>
#define pii pair<ll,ll>
#define PI 3.14159265358979323846
#define MOD 1000000007
#define MOD2 1000000009
#define INF ((ll)1e+18)
#define x1 fldgjdflgjhrthrl
#define x2 fldgjdflgrtyrtyjl
#define y1 fldggfhfghjdflgjl
#define y2 ffgfldgjdflgjl
#define SQ 317
#define MAG 33554431
#define RED 0
#define BLUE 1
#define ALP 26
typedef long long ll;
typedef long double ld;
using namespace std;
ll i,j,k,l,m,r,x,y,K,tot,sz,cur,sum,n,c, maxlvl,q,z,N,ans;
ll a[400500], b[100500], used[100500][15];
vector<ll> g[100500];
pair<ll, pii> queries[100500];
vector<pii> bfs;
int main() {
	//freopen("input.txt","r",stdin);
 	//freopen("input.txt","w",stdout);
    cin >> n >> m;
    for (i = 0; i < m; i++)
    {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    cin >> q;
    for (i = 0; i < q; i++)
        cin >> queries[i].X >> queries[i].Y.X >> queries[i].Y.Y;
    reverse(queries, queries+q);
    for (i = 0; i < q; i++)
    {
        ll v = queries[i].X, d = queries[i].Y.X, c = queries[i].Y.Y;
        if (used[v][d])
            continue;
        bfs.clear();
        bfs.push_back(mp(v,d));
        for (k = 0; k <= d; k++)
            used[v][k] = 1;
        if (a[v] == 0)
            a[v] = c;
        j = 0;
        while (j < bfs.size())
        {
            ll v = bfs[j].X;
            ll d = bfs[j].Y;
            j++;
            if (d == 0)
                continue;
            for (k = 0; k < g[v].size(); k++)
            {
                ll to = g[v][k];
                if (!used[to][d-1])
                {
                    for (l = 0; l <= d-1; l++)
                        used[to][l] = 1;
                    if (a[to] == 0)
                        a[to] = c;
                    bfs.push_back(mp(to, d-1));
                }
            }
        }
    }
    for (i = 1; i <= n; i++)
        cout << a[i] << endl;
    return 0;
}

Submission Info

Judge Result