Submission #1521079
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; const ull mod = 1e9 + 7; #define REP(i,n) for(int i=0;i<(int)n;++i) const int N_MAX=101010; int DP[N_MAX][10]; int A[N_MAX], B[N_MAX]; int main(){ int N, M; cin >> N >> M; REP(i, M){ cin >> A[i] >> B[i]; } int Q; cin >> Q; int c[Q], d[Q], v[Q]; REP(i, Q){ cin >> v[i] >> d[i] >> c[i]; } pii dp[N_MAX][11]; REP(i, Q) dp[v[i]][d[i]] = {i+1, c[i]}; for(int d=10;d>=1;d--){ for(int v=1;v<=N;v++){ dp[v][d-1] = max(dp[v][d-1], dp[v][d]); } REP(i, M){ int a = A[i]; int b = B[i]; dp[a][d-1] = max(dp[a][d-1], dp[b][d]); dp[b][d-1] = max(dp[b][d-1], dp[a][d]); } } REP(i, N) cout << dp[i+1][0].second << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Splatter Painting |
User | theory_and_me |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1013 Byte |
Status | AC |
Exec Time | 330 ms |
Memory | 11264 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 | 3 ms | 8960 KB |
00_example_02.txt | AC | 3 ms | 8960 KB |
10_01.txt | AC | 4 ms | 8960 KB |
10_02.txt | AC | 3 ms | 8960 KB |
10_03.txt | AC | 3 ms | 8960 KB |
10_04.txt | AC | 3 ms | 8960 KB |
10_05.txt | AC | 5 ms | 8960 KB |
10_06.txt | AC | 3 ms | 8960 KB |
10_07.txt | AC | 6 ms | 8960 KB |
10_08.txt | AC | 10 ms | 8960 KB |
10_09.txt | AC | 9 ms | 8960 KB |
10_10.txt | AC | 10 ms | 8960 KB |
10_11.txt | AC | 9 ms | 8960 KB |
10_12.txt | AC | 10 ms | 8960 KB |
10_13.txt | AC | 8 ms | 8960 KB |
10_14.txt | AC | 8 ms | 8960 KB |
10_15.txt | AC | 8 ms | 8960 KB |
10_16.txt | AC | 9 ms | 8960 KB |
10_17.txt | AC | 10 ms | 8960 KB |
20_01.txt | AC | 329 ms | 11264 KB |
20_02.txt | AC | 328 ms | 11264 KB |
20_03.txt | AC | 330 ms | 11264 KB |
20_04.txt | AC | 44 ms | 9216 KB |
20_05.txt | AC | 8 ms | 8960 KB |
20_06.txt | AC | 155 ms | 9216 KB |
20_07.txt | AC | 9 ms | 8960 KB |
20_08.txt | AC | 59 ms | 9856 KB |
20_09.txt | AC | 9 ms | 8960 KB |
20_10.txt | AC | 59 ms | 9856 KB |
20_11.txt | AC | 76 ms | 10112 KB |
20_12.txt | AC | 225 ms | 10112 KB |
20_13.txt | AC | 291 ms | 10880 KB |
20_14.txt | AC | 306 ms | 11136 KB |
20_15.txt | AC | 321 ms | 11008 KB |
20_16.txt | AC | 323 ms | 11264 KB |