Submission #1195326
Source Code Expand
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif
//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }
using Weight = int;
using Flow = int;
struct Edge {
int s, d; Weight w; Flow c;
Edge() {};
Edge(int s, int d, Weight w = 1) : s(s), d(d), w(w), c(w) {};
};
bool operator<(const Edge &e1, const Edge &e2) { return e1.w < e2.w; }
bool operator>(const Edge &e1, const Edge &e2) { return e2 < e1; }
inline ostream &operator<<(ostream &os, const Edge &e) { return (os << '(' << e.s << ", " << e.d << ", " << e.w << ')'); }
using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;
void add_arc(Graph &g, int s, int d, Weight w = 1) {
g[s].emplace_back(s, d, w);
}
void add_edge(Graph &g, int a, int b, Weight w = 1) {
add_arc(g, a, b, w);
add_arc(g, b, a, w);
}
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
int N, M; cin >> N >> M;
Graph g(N);
vector<int> a(M), b(M); rep(i, 0, M) {
cin >> a[i] >> b[i];
a[i]--, b[i]--;
add_edge(g, a[i], b[i]);
}
int Q; cin >> Q;
vector<int> v(Q), d(Q), c(Q);
rep(i, 0, Q) {
cin >> v[i] >> d[i] >> c[i];
v[i]--;
}
vector<int> color(N);
vector<int> cnt(N);
auto bfs = [&](int root, int d, int c) {
int n = g.size();
vector<bool> f(n);
using State = tuple<int, int>;
queue<State> q; q.emplace(root, d);
while (q.size()) {
int u, d;
tie(u, d) = q.front(); q.pop();
if (f[u])continue;
f[u] = true;
if (color[u] == 0)color[u] = c;
cnt[u] = d;
if (d == 0)continue;
for (auto &e : g[u]) {
if (f[e.d])continue;
if (cnt[e.d] >= 1)continue;
q.emplace(e.d, d - 1);
}
}
};
rrep(i, 0, Q) {
bfs(v[i], d[i], c[i]);
}
rep(i, 0, color.size()) { cout << color[i] << endl; }
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Splatter Painting |
User |
minaminao |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2318 Byte |
Status |
WA |
Exec Time |
298 ms |
Memory |
11248 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
0 / 200 |
0 / 500 |
Status |
|
|
|
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 |
1 ms |
256 KB |
00_example_02.txt |
AC |
1 ms |
256 KB |
10_01.txt |
AC |
2 ms |
384 KB |
10_02.txt |
AC |
1 ms |
256 KB |
10_03.txt |
AC |
1 ms |
256 KB |
10_04.txt |
AC |
1 ms |
256 KB |
10_05.txt |
AC |
2 ms |
384 KB |
10_06.txt |
AC |
1 ms |
256 KB |
10_07.txt |
AC |
4 ms |
256 KB |
10_08.txt |
WA |
6 ms |
512 KB |
10_09.txt |
WA |
6 ms |
512 KB |
10_10.txt |
WA |
6 ms |
512 KB |
10_11.txt |
WA |
6 ms |
512 KB |
10_12.txt |
WA |
6 ms |
512 KB |
10_13.txt |
WA |
5 ms |
384 KB |
10_14.txt |
WA |
5 ms |
384 KB |
10_15.txt |
WA |
4 ms |
384 KB |
10_16.txt |
AC |
5 ms |
512 KB |
10_17.txt |
AC |
6 ms |
512 KB |
20_01.txt |
WA |
298 ms |
11008 KB |
20_02.txt |
WA |
298 ms |
11008 KB |
20_03.txt |
WA |
296 ms |
11008 KB |
20_04.txt |
AC |
23 ms |
2960 KB |
20_05.txt |
WA |
5 ms |
384 KB |
20_06.txt |
AC |
149 ms |
3584 KB |
20_07.txt |
WA |
5 ms |
384 KB |
20_08.txt |
AC |
36 ms |
1664 KB |
20_09.txt |
WA |
5 ms |
384 KB |
20_10.txt |
WA |
43 ms |
1152 KB |
20_11.txt |
AC |
53 ms |
1792 KB |
20_12.txt |
WA |
175 ms |
8832 KB |
20_13.txt |
WA |
260 ms |
9984 KB |
20_14.txt |
WA |
269 ms |
9984 KB |
20_15.txt |
AC |
287 ms |
11120 KB |
20_16.txt |
AC |
286 ms |
11248 KB |