Submission #1368981


Source Code Expand

#include <bits/stdc++.h>
 
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long 
#define ld long double
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
 
#define y1 what

using namespace std;
 
const int N = (int) 2e5 + 10;
const int M = (int) 18;
const ll big =  (1LL << 51);
const ll LINF = (ll) 1e18;
const int INF = (int) 1e9 + 7;
const double EPS = (double) 1e-6;
const double PI =  3.14159265359;

int n, m, q;
int a[N], b[N], c[N], d[N];
vector<int> v[N], comp[N];
int was[N], clr[N];

int main() {
    #define fn "balls"
    #ifdef witch
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
//        freopen(fn".in", "r", stdin);
//        freopen(fn".out", "w", stdout);
    #endif
    srand(time(0));
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    for (int i = q; i >= 1; i--) {
        if (was[a[i]])
            continue;
        queue<int> q;
        q.push(a[i]);
        d[a[i]] = b[i];
        was[a[i]] = c[i];
        clr[a[i]] = i;
        vector<int> all;
        while (!q.empty()) {
            int fr = q.front();
            all.pb(fr);
            q.pop();
            if (d[fr] == 0) 
                continue;
            for (auto it : v[fr]) {
                if (was[it]) {
                    if (clr[it] == clr[a[i]]) 
                        continue;
                    if (d[fr] - c[clr[it]] - 2 >= 0) {
                        for (auto go : comp[clr[it]]) {
                            if (!was[go]) {
                                was[go] = c[i];
                                clr[go] = i;
                                d[go] = d[fr] - 1;  
                                q.push(go);
                            }
                        }
                    }
                } else {
                    was[it] = c[i];
                    d[it] = d[fr] - 1;
                    clr[it] = i;
                    q.push(it);
                }
            }
        }
        for (auto it : all) {
            for (auto add : v[it]) {
                if (!was[add])
                    comp[i].pb(add);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << was[i] << "\n";
    }
    return 0;
}

Submission Info

Submission Time
Task B - Splatter Painting
User Nurlykhan
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2567 Byte
Status WA
Exec Time 160 ms
Memory 17272 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 500
Status
AC × 2
AC × 10
WA × 9
AC × 16
WA × 19
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 4 ms 11008 KB
00_example_02.txt AC 4 ms 11008 KB
10_01.txt AC 5 ms 11008 KB
10_02.txt AC 4 ms 11008 KB
10_03.txt WA 4 ms 11008 KB
10_04.txt AC 4 ms 11008 KB
10_05.txt AC 5 ms 11008 KB
10_06.txt AC 4 ms 11008 KB
10_07.txt AC 4 ms 11008 KB
10_08.txt WA 7 ms 11136 KB
10_09.txt WA 7 ms 11136 KB
10_10.txt WA 7 ms 11136 KB
10_11.txt WA 7 ms 11136 KB
10_12.txt WA 7 ms 11136 KB
10_13.txt WA 6 ms 11008 KB
10_14.txt WA 5 ms 11008 KB
10_15.txt WA 5 ms 11008 KB
10_16.txt AC 7 ms 11136 KB
10_17.txt AC 7 ms 11136 KB
20_01.txt WA 158 ms 15984 KB
20_02.txt WA 160 ms 16000 KB
20_03.txt WA 159 ms 15896 KB
20_04.txt AC 28 ms 11776 KB
20_05.txt WA 8 ms 11008 KB
20_06.txt AC 17 ms 12032 KB
20_07.txt WA 8 ms 11008 KB
20_08.txt AC 49 ms 11648 KB
20_09.txt WA 8 ms 11008 KB
20_10.txt WA 49 ms 11520 KB
20_11.txt AC 63 ms 11904 KB
20_12.txt WA 87 ms 15104 KB
20_13.txt WA 142 ms 15872 KB
20_14.txt WA 149 ms 15872 KB
20_15.txt AC 147 ms 17272 KB
20_16.txt AC 146 ms 17272 KB