oj.uz

Submission #171416

# Submission time Handle Problem Language Result Execution time Memory
171416 2019-12-28T15:57:17 Z kuroni Synchronization (JOI13_synchronization) C++17
100 / 100
 4163 ms 19628 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(2 * 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 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 5212 KB Output is correct
7 Correct 79 ms 6008 KB Output is correct
8 Correct 80 ms 6044 KB Output is correct
9 Correct 82 ms 6048 KB Output is correct
10 Correct 3877 ms 14320 KB Output is correct
11 Correct 3680 ms 14280 KB Output is correct
12 Correct 2796 ms 14708 KB Output is correct
13 Correct 4083 ms 13988 KB Output is correct
14 Correct 3318 ms 14396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1591 ms 17156 KB Output is correct
2 Correct 1573 ms 17116 KB Output is correct
3 Correct 1159 ms 18980 KB Output is correct
4 Correct 1179 ms 19048 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 5116 KB Output is correct
5 Correct 7 ms 5032 KB Output is correct
6 Correct 8 ms 5208 KB Output is correct
7 Correct 59 ms 6012 KB Output is correct
8 Correct 2731 ms 14784 KB Output is correct
9 Correct 2389 ms 14764 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2565 ms 14776 KB Output is correct
2 Correct 1239 ms 19412 KB Output is correct
3 Correct 1199 ms 19440 KB Output is correct
4 Correct 1186 ms 19628 KB Output is correct

Subtask #5
40.0 / 40.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 9 ms 5112 KB Output is correct
6 Correct 82 ms 6084 KB Output is correct
7 Correct 4163 ms 14504 KB Output is correct
8 Correct 3030 ms 14768 KB Output is correct
9 Correct 3853 ms 14956 KB Output is correct
10 Correct 2877 ms 15184 KB Output is correct
11 Correct 1620 ms 17796 KB Output is correct
12 Correct 1594 ms 17988 KB Output is correct
13 Correct 1161 ms 19448 KB Output is correct