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
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 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