Submission #1351771


Source Code Expand

#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;

int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<vector<int> > g(n);
    repeat (i, m) {
        int a, b; scanf("%d%d", &a, &b); -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int q; scanf("%d", &q);
    vector<int> v(q), d(q), c(q); repeat (t, q) { scanf("%d%d%d", &v[t], &d[t], &c[t]); -- v[t]; }
    // solve
    vector<int> result(n);
    vector<int> used(n, -1);
    repeat_reverse (t, q) {
        queue<int> que;
        auto push = [&](int i, int dist) {
            if (used[i] < dist) {
                used[i] = dist;
                if (not result[i]) result[i] = c[t];
                que.emplace(i);
            }
        };
        push(v[t], d[t]);
        while (not que.empty()) {
            int i = que.front(); que.pop();
            if (used[i] != 0) {
                for (int j : g[i]) {
                    push(j, used[i]-1);
                }
            }
        }
    }
    // output
    repeat (i, n) {
        printf("%d\n", result[i]);
    }
    return 0;
}

Submission Info

Submission Time
Task B - Splatter Painting
User kimiyuki
Language C++14 (Clang 3.8.0)
Score 700
Code Size 1309 Byte
Status AC
Exec Time 94 ms
Memory 8824 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 7 ms 888 KB
00_example_02.txt AC 1 ms 256 KB
10_01.txt AC 1 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 1 ms 256 KB
10_06.txt AC 1 ms 256 KB
10_07.txt AC 1 ms 256 KB
10_08.txt AC 3 ms 384 KB
10_09.txt AC 3 ms 384 KB
10_10.txt AC 3 ms 384 KB
10_11.txt AC 3 ms 384 KB
10_12.txt AC 3 ms 384 KB
10_13.txt AC 2 ms 384 KB
10_14.txt AC 2 ms 384 KB
10_15.txt AC 2 ms 384 KB
10_16.txt AC 2 ms 384 KB
10_17.txt AC 2 ms 384 KB
20_01.txt AC 88 ms 7808 KB
20_02.txt AC 94 ms 7808 KB
20_03.txt AC 93 ms 7680 KB
20_04.txt AC 13 ms 1152 KB
20_05.txt AC 3 ms 384 KB
20_06.txt AC 12 ms 3456 KB
20_07.txt AC 3 ms 384 KB
20_08.txt AC 18 ms 1152 KB
20_09.txt AC 3 ms 384 KB
20_10.txt AC 18 ms 1152 KB
20_11.txt AC 23 ms 1536 KB
20_12.txt AC 48 ms 6400 KB
20_13.txt AC 74 ms 7424 KB
20_14.txt AC 81 ms 7552 KB
20_15.txt AC 68 ms 8696 KB
20_16.txt AC 69 ms 8824 KB