Submission #1494047

---

Source Code Expand

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>  
using namespace std;
#define eps 0.00000001
#define LONG_INF 10000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define f(n) for(int i=0;i<n;++i)
#define REP(i,n) for(long long i = 0;i < n;++i)
int maxium[1000000] = {};
int color[1000000] = {};
vector<int> vertex[1000000];
int main() {
	int n, m,query;
	cin >> n >> m;
	REP(i, m) {
		int a, b;
		cin >> a >> b;
		vertex[a].push_back(b);
		vertex[b].push_back(a);
	}
	vector<pair<int, int>> hoge;
	vector<int> colorful;
	cin >> query;
	REP(i, query) {
		int a, b;
		cin >> a >> b;
		hoge.push_back(make_pair(a, b));
		int c;
		cin >> c;
		colorful.push_back(c);
	}
	reverse(colorful.begin(), colorful.end());
	reverse(hoge.begin(), hoge.end());
	for (int i = 0;i < query;++i) {
		if (maxium[hoge[i].first] < hoge[i].second+1) {
			queue<pair<int, int>> nya;
			map<int, int> visited;
			nya.push(make_pair(hoge[i].first, hoge[i].second+1));
			maxium[hoge[i].first] = hoge[i].second + 1;
			while (nya.empty() == false) {
				pair<int, int> now = nya.front();nya.pop();
				if (visited[now.first] == false) {
					visited[now.first] = true;
					if (color[now.first] == 0)color[now.first] = colorful[i] + 1;
					now.second--;
					if (now.second != 0) {
						for (int q = 0;q < vertex[now.first].size();++q) {
							if (maxium[vertex[now.first][q]] < now.second) {
								maxium[vertex[now.first][q]] = now.second;
								nya.push(make_pair(vertex[now.first][q], now.second));
							}
						}
					}
				}
			}
		}
	}
	for (int i = 1;i <= n;++i) {
		cout << max(color[i] - 1,0) << endl;
	}
	return 0;
}

Submission Info

Judge Result