Submission #1198498


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define rep(i, j) for(int i=0; i < (int)(j); i++)

template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }

const int MAX_D = 10;

class Solver {
  public:    
    bool solve() {
        int N, M; cin >> N >> M;
        vector<vector<int>> E(N);
        rep(i, M) {
            int a, b; cin >> a >> b;
            a--; b--;
            E[a].push_back(b);
            E[b].push_back(a);
        }
        
        int Q; cin >> Q;
        vector<int> V(Q), D(Q), C(Q);
        rep(i, Q) {
            cin >> V[i] >> D[i] >> C[i];
            V[i]--;
        }
        
        vector<vector<int>> dp(N, vector<int>(MAX_D + 1, -1));

        function<void(int, int, int)> paint = [&] (int node, int time, int dist) {
            if(dist < 0 or dp[node][dist] >= 0) return;
            dp[node][dist] = time;
            for(int nxt : E[node]) paint(nxt, time, dist - 1);
        };
        
        for(int q = Q - 1; q >= 0; q--) paint(V[q], q, D[q]);

        rep(i, N) {
            int time = -1;
            rep(t, MAX_D + 1) set_max(time, dp[i][t]);
            cout << (time >= 0 ? C[time] : 0) << endl;
        }
        
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}

Submission Info

Submission Time
Task B - Splatter Painting
User cormoran
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1507 Byte
Status AC
Exec Time 289 ms
Memory 16248 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 1 ms 256 KB
00_example_02.txt AC 1 ms 256 KB
10_01.txt AC 2 ms 256 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 256 KB
10_06.txt AC 1 ms 256 KB
10_07.txt AC 4 ms 512 KB
10_08.txt AC 6 ms 512 KB
10_09.txt AC 6 ms 512 KB
10_10.txt AC 6 ms 512 KB
10_11.txt AC 6 ms 512 KB
10_12.txt AC 6 ms 512 KB
10_13.txt AC 5 ms 512 KB
10_14.txt AC 5 ms 512 KB
10_15.txt AC 5 ms 512 KB
10_16.txt AC 6 ms 640 KB
10_17.txt AC 5 ms 640 KB
20_01.txt AC 272 ms 15616 KB
20_02.txt AC 289 ms 15488 KB
20_03.txt AC 285 ms 15488 KB
20_04.txt AC 30 ms 1664 KB
20_05.txt AC 4 ms 384 KB
20_06.txt AC 153 ms 10880 KB
20_07.txt AC 4 ms 384 KB
20_08.txt AC 19 ms 1280 KB
20_09.txt AC 4 ms 512 KB
20_10.txt AC 18 ms 1152 KB
20_11.txt AC 24 ms 1536 KB
20_12.txt AC 202 ms 13440 KB
20_13.txt AC 226 ms 14848 KB
20_14.txt AC 244 ms 14592 KB
20_15.txt AC 263 ms 16120 KB
20_16.txt AC 267 ms 16248 KB