Submission #1194719


Source Code Expand

// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>

using namespace std;

#define rep(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool smin(T &a, const T &b)   { return a > b ? a = b : a;    }
template<typename T> inline bool smax(T &a, const T &b)   { return a < b ? a = b : a;    }

typedef long long LL;

const int N = (int) 1e6 + 6, mod = (int) 0;

set<int> all[N];
int qv[N], qd[N], qc[N], q[N * 10], seen[N], res[N];
vector<int> adj[N];
int main() {
	ios_base::sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	memset(seen, -1, sizeof seen);
	for (int j = 0; j < m; ++j) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int qn;
	cin >> qn;
	for (int j = 0; j < qn; ++j) {
		cin >> qv[j] >> qd[j] >> qc[j];
		--qv[j];
	}
	for (int j = qn - 1; j >= 0; --j) {
		int h = 0, t = 0;
		if (seen[qv[j]] < qd[j]) {
			seen[qv[j]] = qd[j];
			q[t++] = qv[j];
		}
		while (h != t) {
			int v = q[h++];
			if (!res[v]) {
				res[v] = qc[j];
			}
			if (seen[v] <= 0) {
				continue;
			}
			for (int u : adj[v]) {
				if (seen[u] < seen[v] - 1) {
					seen[u] = seen[v] - 1;
					q[t++] = u;
				}
			}
		}
	}
	for (int j = 0; j < n; ++j)
		cout << res[j] << '\n';

}

Submission Info

Submission Time
Task B - Splatter Painting
User Reyna
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1998 Byte
Status AC
Exec Time 109 ms
Memory 88056 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 500 / 500
Status
AC × 2
AC × 19
AC × 35
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt
Subtask1 00_example_01.txt, 00_example_02.txt, 10_01.txt, 10_02.txt, 10_03.txt, 10_04.txt, 10_05.txt, 10_06.txt, 10_07.txt, 10_08.txt, 10_09.txt, 10_10.txt, 10_11.txt, 10_12.txt, 10_13.txt, 10_14.txt, 10_15.txt, 10_16.txt, 10_17.txt
All 00_example_01.txt, 00_example_02.txt, 10_01.txt, 10_02.txt, 10_03.txt, 10_04.txt, 10_05.txt, 10_06.txt, 10_07.txt, 10_08.txt, 10_09.txt, 10_10.txt, 10_11.txt, 10_12.txt, 10_13.txt, 10_14.txt, 10_15.txt, 10_16.txt, 10_17.txt, 20_01.txt, 20_02.txt, 20_03.txt, 20_04.txt, 20_05.txt, 20_06.txt, 20_07.txt, 20_08.txt, 20_09.txt, 20_10.txt, 20_11.txt, 20_12.txt, 20_13.txt, 20_14.txt, 20_15.txt, 20_16.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 29 ms 84096 KB
00_example_02.txt AC 29 ms 84096 KB
10_01.txt AC 29 ms 84096 KB
10_02.txt AC 29 ms 84096 KB
10_03.txt AC 29 ms 84096 KB
10_04.txt AC 29 ms 84096 KB
10_05.txt AC 29 ms 84096 KB
10_06.txt AC 29 ms 84096 KB
10_07.txt AC 29 ms 84096 KB
10_08.txt AC 31 ms 84224 KB
10_09.txt AC 31 ms 84224 KB
10_10.txt AC 30 ms 84224 KB
10_11.txt AC 31 ms 84224 KB
10_12.txt AC 31 ms 84224 KB
10_13.txt AC 30 ms 84224 KB
10_14.txt AC 30 ms 84224 KB
10_15.txt AC 30 ms 84224 KB
10_16.txt AC 30 ms 84224 KB
10_17.txt AC 30 ms 84224 KB
20_01.txt AC 108 ms 87296 KB
20_02.txt AC 108 ms 87296 KB
20_03.txt AC 109 ms 87296 KB
20_04.txt AC 40 ms 84864 KB
20_05.txt AC 31 ms 84096 KB
20_06.txt AC 36 ms 84352 KB
20_07.txt AC 31 ms 84096 KB
20_08.txt AC 45 ms 84224 KB
20_09.txt AC 30 ms 84096 KB
20_10.txt AC 45 ms 84096 KB
20_11.txt AC 50 ms 84224 KB
20_12.txt AC 72 ms 87296 KB
20_13.txt AC 92 ms 87424 KB
20_14.txt AC 98 ms 87424 KB
20_15.txt AC 87 ms 87800 KB
20_16.txt AC 89 ms 88056 KB