Submission #1368955
Source Code Expand
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
/** Interface */
inline int readChar();
template <class T = int> inline T readInt();
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x );
inline void writeWord( const char *s );
/** Read */
static const int buf_size = 4096;
inline int getChar() {
static char buf[buf_size];
static int len = 0, pos = 0;
if (pos == len) {
pos = 0, len = fread(buf, 1, buf_size, stdin);
}
if (pos == len) {
return -1;
}
return buf[pos++];
}
inline int readChar() {
int c = getChar();
while (c <= 32) {
c = getChar();
}
return c;
}
template <class T>
inline T readInt() {
int s = 1, c = readChar();
T x = 0;
if (c == '-')
s = -1, c = getChar();
while ('0' <= c && c <= '9')
x = x * 10 + c - '0', c = getChar();
return s == 1 ? x : -x;
}
/** Write */
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar( int x ) {
if (write_pos == buf_size)
fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt( T x, char end ) {
if (x < 0)
writeChar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n)
s[n++] = '0' + x % 10, x /= 10;
while (n--)
writeChar(s[n]);
if (end)
writeChar(end);
}
inline void writeWord( const char *s ) { while (*s)
writeChar(*s++); }
struct Flusher {
~Flusher() {
if (write_pos)
fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
}
} flusher;
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define ll long long
#define ld double
#define ull unsigned long long
#define PI pair < int, int >
const int N = 5e5 + 123;
const int M = 2e5;
const ld Pi = acos(-1);
const ll inf = 1e18;
const int mod = 1e9 + 7;
const int Sz = 501;
const int MOD = 1e9 + 7;
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
}
int mult(int a, int b) {
return 1ll * a * b % mod;
}
int sum(int a, int b) {
add(a, b);
return a;
}
int n, m, q, ans[N], a[N], b[N];
vector < int > g[N];
struct Query {
int v, d, c;
} Q[N];
void solve() {
cin >> n >> m;
for (int i = 1;i <= m;i++) {
int u, v; cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
cin >> q;
for (int i = 1;i <= q;i++) {
cin >> Q[i].v >> Q[i].d >> Q[i].c;
}
for (int len = 0;len <= 10;len++) {
for (int i = 1;i <= q;i++) {
if (Q[i].d == len) {
a[Q[i].v] = max(a[Q[i].v], i);
}
}
for (int it = 0;it < len;it++) {
for (int i = 1;i <= n;i++) b[i] = a[i];
for (int i = 1;i <= n;i++) {
for (auto j : g[i]) a[i] = max(a[i], b[j]);
}
}
for (int i = 1;i <= n;i++) {
ans[i] = max(ans[i], a[i]);
a[i] = 0;
}
}
for (int i = 1;i <= n;i++) cout << Q[ans[i]].c << "\n";
}
int main() {
#ifdef wws
freopen("in", "r", stdin);
// freopen("in", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
int tt = 1;
while(tt--) solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Splatter Painting |
User |
SmallBoy |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
4030 Byte |
Status |
AC |
Exec Time |
129 ms |
Memory |
23800 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
200 / 200 |
500 / 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 |
6 ms |
18688 KB |
00_example_02.txt |
AC |
6 ms |
18688 KB |
10_01.txt |
AC |
6 ms |
18688 KB |
10_02.txt |
AC |
6 ms |
18688 KB |
10_03.txt |
AC |
6 ms |
18688 KB |
10_04.txt |
AC |
6 ms |
18688 KB |
10_05.txt |
AC |
6 ms |
18688 KB |
10_06.txt |
AC |
6 ms |
18688 KB |
10_07.txt |
AC |
6 ms |
18688 KB |
10_08.txt |
AC |
8 ms |
18816 KB |
10_09.txt |
AC |
8 ms |
18816 KB |
10_10.txt |
AC |
8 ms |
18816 KB |
10_11.txt |
AC |
8 ms |
18816 KB |
10_12.txt |
AC |
8 ms |
18816 KB |
10_13.txt |
AC |
8 ms |
18816 KB |
10_14.txt |
AC |
7 ms |
18816 KB |
10_15.txt |
AC |
7 ms |
18816 KB |
10_16.txt |
AC |
8 ms |
18816 KB |
10_17.txt |
AC |
7 ms |
18816 KB |
20_01.txt |
AC |
128 ms |
23040 KB |
20_02.txt |
AC |
129 ms |
23040 KB |
20_03.txt |
AC |
128 ms |
23040 KB |
20_04.txt |
AC |
26 ms |
19456 KB |
20_05.txt |
AC |
7 ms |
18816 KB |
20_06.txt |
AC |
24 ms |
18944 KB |
20_07.txt |
AC |
8 ms |
18816 KB |
20_08.txt |
AC |
25 ms |
19700 KB |
20_09.txt |
AC |
7 ms |
18816 KB |
20_10.txt |
AC |
24 ms |
19584 KB |
20_11.txt |
AC |
30 ms |
19968 KB |
20_12.txt |
AC |
95 ms |
22016 KB |
20_13.txt |
AC |
114 ms |
22912 KB |
20_14.txt |
AC |
116 ms |
23040 KB |
20_15.txt |
AC |
104 ms |
23544 KB |
20_16.txt |
AC |
104 ms |
23800 KB |