oj.uz

Submission #171412

# Submission time Handle Problem Language Result Execution time Memory
171412 2019-12-28T15:46:19 Z kuroni Synchronization (JOI13_synchronization) C++17
100 / 100
 6394 ms 21868 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(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 7 ms 5116 KB Output is correct
6 Correct 10 ms 5240 KB Output is correct
7 Correct 106 ms 6256 KB Output is correct
8 Correct 104 ms 6236 KB Output is correct
9 Correct 103 ms 6264 KB Output is correct
10 Correct 5868 ms 16712 KB Output is correct
11 Correct 5265 ms 16816 KB Output is correct
12 Correct 4094 ms 17096 KB Output is correct
13 Correct 4703 ms 15980 KB Output is correct
14 Correct 4189 ms 16256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1954 ms 17300 KB Output is correct
2 Correct 1862 ms 19052 KB Output is correct
3 Correct 1393 ms 20652 KB Output is correct
4 Correct 1384 ms 20796 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 5068 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 9 ms 5212 KB Output is correct
7 Correct 80 ms 6280 KB Output is correct
8 Correct 3803 ms 17456 KB Output is correct
9 Correct 4467 ms 17440 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3759 ms 14980 KB Output is correct
2 Correct 1394 ms 21752 KB Output is correct
3 Correct 1395 ms 21788 KB Output is correct
4 Correct 1438 ms 21712 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 10 ms 5240 KB Output is correct
6 Correct 110 ms 6392 KB Output is correct
7 Correct 6394 ms 17064 KB Output is correct
8 Correct 4077 ms 17396 KB Output is correct
9 Correct 3765 ms 17168 KB Output is correct
10 Correct 3945 ms 17428 KB Output is correct
11 Correct 1934 ms 20436 KB Output is correct
12 Correct 2198 ms 20080 KB Output is correct
13 Correct 1543 ms 21868 KB Output is correct