oj.uz

Submission #171418

# Submission time Handle Problem Language Result Execution time Memory
171418 2019-12-28T15:59:40 Z kuroni Synchronization (JOI13_synchronization) C++17
100 / 100
 4500 ms 19612 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1E5 + 5, M = 2E5 + 5;

int n, m, q, d, u, f[N], g[N], ue[N], ve[N], lz[N], col[N];
int que[M];
bool chk[N], mod[N];
vector<int> adj[N], com[N];

void init() {
    for (int i = 1; i <= n; i++) {
        lz[i] = col[i] = 0;
        mod[i] = false;
        adj[i].clear(); com[i].clear();
    }
}

void DFS(int u, int p = 0) {
    col[u] = col[p];
    for (int &v : adj[u]) {
        int c = u ^ ue[v] ^ ve[v];
        if (c != p) {
            DFS(c, u);
        }
    }
}

void update(int u, int dif, int p = 0) {
    f[u] += dif; lz[u] += dif;
    for (int &v : com[u]) {
        int c = u ^ col[ue[v]] ^ col[ve[v]];
        if (!chk[v]) {
            g[v] += dif;
        } else if (c != p) {
            update(c, dif, u);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    fill(f + 1, f + n + 1, 1);
    for (int i = 1; i < n; i++) {
        cin >> ue[i] >> ve[i];
        g[i] = 2;
    }
    for (int i = 1; i <= m; i++) {
        cin >> que[i];
    }
    d = sqrt(4 * m);
    for (int bl = 1; bl <= m; bl += d) {
        init();
        for (int i = 0; i < d && bl + i <= m; i++) {
            mod[que[bl + i]] = true;
        }
        for (int i = 1; i < n; i++) {
            if (!mod[i] && chk[i]) {
                adj[ue[i]].push_back(i);
                adj[ve[i]].push_back(i);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (col[i] == 0) {
                col[0] = i;
                DFS(i);
            }
        }
        for (int i = 1; i < n; i++) {
            if (mod[i]) {
                com[col[ue[i]]].push_back(i);
                com[col[ve[i]]].push_back(i);
            }
        }
        for (int i = 0; i < d && bl + i <= m; i++) {
            int e = que[bl + i];
            if (!chk[e]) {
                int sum = (f[col[ue[e]]] + f[col[ve[e]]] + g[e]) / 2;
                update(col[ue[e]], sum - f[col[ue[e]]]);
                update(col[ve[e]], sum - f[col[ve[e]]]);
                g[e] = 0;
            }
            chk[e] = !chk[e];
        }
        for (int i = 1; i <= n; i++) {
            f[i] = f[col[i]];
        }
        for (int i = 1; i < n; i++) {
            if (!mod[i] && !chk[i]) {
                g[i] += lz[col[ue[i]]] + lz[col[ve[i]]];
            }
        }
    }
    while (q--) {
        cin >> u;
        cout << f[u] << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 8 ms 5112 KB Output is correct
7 Correct 61 ms 5980 KB Output is correct
8 Correct 60 ms 6008 KB Output is correct
9 Correct 63 ms 6056 KB Output is correct
10 Correct 2779 ms 14284 KB Output is correct
11 Correct 2634 ms 14188 KB Output is correct
12 Correct 1823 ms 14564 KB Output is correct
13 Correct 4500 ms 14028 KB Output is correct
14 Correct 2260 ms 14304 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1477 ms 17280 KB Output is correct
2 Correct 1456 ms 17264 KB Output is correct
3 Correct 1194 ms 18864 KB Output is correct
4 Correct 1131 ms 18940 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 8 ms 5112 KB Output is correct
7 Correct 47 ms 6008 KB Output is correct
8 Correct 2061 ms 14764 KB Output is correct
9 Correct 2305 ms 14664 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2400 ms 14812 KB Output is correct
2 Correct 1151 ms 19368 KB Output is correct
3 Correct 1177 ms 19612 KB Output is correct
4 Correct 1128 ms 19544 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 9 ms 5132 KB Output is correct
6 Correct 64 ms 6008 KB Output is correct
7 Correct 2588 ms 14532 KB Output is correct
8 Correct 1837 ms 14872 KB Output is correct
9 Correct 4391 ms 14708 KB Output is correct
10 Correct 2327 ms 15380 KB Output is correct
11 Correct 1476 ms 17904 KB Output is correct
12 Correct 1485 ms 17856 KB Output is correct
13 Correct 1142 ms 19576 KB Output is correct