Submission #1195285
Source Code Expand
#include <bits/stdc++.h> typedef long long int ll; typedef unsigned long long int ull; #define rep(i,n) for(ll i=0;i<(n);i++) using namespace std; struct Node{ ll pos; ll cost; bool operator< (const Node &r) const{ return cost > r.cost; } }; ll NODE_MAX = pow(10, 5) + 5; ll INF = NODE_MAX + 5; vector<ll> dijkstra(ll src, vector<ll>* g){ priority_queue<Node> que; que.push({src,0}); vector<ll> res(NODE_MAX,INF); while(que.size()){ Node n = que.top(); que.pop(); if(res[n.pos] == INF) res[n.pos] = n.cost; else continue; for(auto e : g[n.pos]){ que.push({e, n.cost + 1}); } } return res; } int main(){ ll n, m; cin >> n >> m; vector<ll> g[n+5]; rep(i, m){ ll a, b; cin >> a >> b; g[a-1].push_back(b-1); g[b-1].push_back(a-1); } vector<vector<set<ll>>> memo(n, vector<set<ll>>(n, set<ll>())); rep(src, n){ vector<ll> res = dijkstra(src, g); rep(to, n){ ll cost = res[to]; if(cost < INF){ memo[src][cost].insert(to); memo[to][cost].insert(src); } } } vector<ll> color(n, 0); ll q; cin >> q; rep(i, q){ ll v, d, c; cin >> v >> d >> c; v--; rep(cost, d+1){ for(auto e : memo[v][cost]) color[e] = c; } } rep(i, n){ cout << color[i] << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Splatter Painting |
User | npz35 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1621 Byte |
Status | RE |
Exec Time | 3488 ms |
Memory | 376304 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 | 2 ms | 1024 KB |
00_example_02.txt | AC | 2 ms | 1024 KB |
10_01.txt | AC | 27 ms | 2416 KB |
10_02.txt | AC | 7 ms | 1792 KB |
10_03.txt | AC | 5 ms | 1280 KB |
10_04.txt | AC | 7 ms | 1664 KB |
10_05.txt | AC | 27 ms | 2416 KB |
10_06.txt | RE | 266 ms | 1024 KB |
10_07.txt | AC | 153 ms | 140160 KB |
10_08.txt | TLE | 2120 ms | 303600 KB |
10_09.txt | TLE | 2122 ms | 313456 KB |
10_10.txt | TLE | 2122 ms | 309488 KB |
10_11.txt | MLE | 1992 ms | 303472 KB |
10_12.txt | TLE | 2122 ms | 311664 KB |
10_13.txt | TLE | 2123 ms | 331504 KB |
10_14.txt | TLE | 2123 ms | 328304 KB |
10_15.txt | TLE | 2122 ms | 318704 KB |
10_16.txt | TLE | 2126 ms | 376304 KB |
10_17.txt | TLE | 2126 ms | 376304 KB |
20_01.txt | TLE | 2292 ms | -485564 KB |
20_02.txt | TLE | 2603 ms | -485276 KB |
20_03.txt | RE | 1769 ms | -485044 KB |
20_04.txt | TLE | 2245 ms | -1866012 KB |
20_05.txt | AC | 113 ms | 23792 KB |
20_06.txt | RE | 1804 ms | -485504 KB |
20_07.txt | AC | 86 ms | 25316 KB |
20_08.txt | AC | 1559 ms | 23824 KB |
20_09.txt | AC | 78 ms | 40048 KB |
20_10.txt | AC | 178 ms | 8560 KB |
20_11.txt | TLE | 2107 ms | 50264 KB |
20_12.txt | RE | 1997 ms | -485504 KB |
20_13.txt | TLE | 3488 ms | -485208 KB |
20_14.txt | RE | 1789 ms | -485028 KB |
20_15.txt | RE | 1609 ms | -485036 KB |
20_16.txt | RE | 1596 ms | -485340 KB |