oj.uz

Submission #819380

# Submission time Handle Problem Language Result Execution time Memory
819380 2023-08-10T09:59:05 Z boyliguanhan Synchronization (JOI13_synchronization) C++17
100 / 100
 229 ms 24240 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
bool on[100100];
vector<int> adj[100100];
int ans[100100], pre[100100], cnt = 1, ti[100100], to[100100], bj[100100][20], tree[100100], E[200100][2];
void dfs(int n, int p) {
    bj[n][0] = p;
    for (int i = 1; i < 20; i++)
        bj[n][i] = bj[bj[n][i - 1]][i - 1];
    ans[n] = 1;
    ti[n] = cnt++;
    for (int i : adj[n])
        if (i-p)
            dfs(i, n);
    to[n] = cnt;
}
void U(int n, int val) {
    while(n < 100100)
        tree[n] += val, n+=n&-n;
}
int Q(int n) {
    int ans = 0;
    while(n)
        ans += tree[n], n-=n&-n;
    return ans;
}
int gr(int n) {
    int lca = n;
    for (int i = 20; i--;)
        if (Q(ti[bj[lca][i]]) == Q(ti[n]))
            lca = bj[lca][i];
    return lca;
}
int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++) {
        cin >> E[i][0] >> E[i][1];
        adj[E[i][0]].push_back(E[i][1]);
        adj[E[i][1]].push_back(E[i][0]);
    }
    dfs(1,1);
    for(int i = 1; i < n; i++) {
        if(bj[E[i][0]][0]==E[i][1])
            swap(E[i][0], E[i][1]);
    }
    for(int i = 1; i <= n; i++) {
        U(ti[i], -1);
        U(to[i], 1);
    }
    while (m--) {
        int x;
        cin >> x;
        int u = E[x][0], v = E[x][1];
        if (bj[u][0] == v) swap(u, v);
                if (on[x]) {
            ans[v] = pre[v] = ans[gr(u)];
            U(ti[v], -1);
            U(to[v], 1);
        } else {
            ans[gr(u)] += ans[v] - pre[v];
            U(ti[v], 1);
            U(to[v], -1);
        }
        on[x] = !on[x];
    }
    while (q--) {
        int x;
        cin >> x;
        cout << ans[gr(x)] << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 13 ms 4292 KB Output is correct
8 Correct 12 ms 4208 KB Output is correct
9 Correct 12 ms 4208 KB Output is correct
10 Correct 191 ms 18864 KB Output is correct
11 Correct 206 ms 18904 KB Output is correct
12 Correct 174 ms 23444 KB Output is correct
13 Correct 82 ms 18776 KB Output is correct
14 Correct 134 ms 17840 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 20748 KB Output is correct
2 Correct 81 ms 20428 KB Output is correct
3 Correct 79 ms 22548 KB Output is correct
4 Correct 83 ms 22544 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2900 KB Output is correct
7 Correct 17 ms 4808 KB Output is correct
8 Correct 228 ms 24140 KB Output is correct
9 Correct 229 ms 24184 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 24164 KB Output is correct
2 Correct 128 ms 23492 KB Output is correct
3 Correct 140 ms 23672 KB Output is correct
4 Correct 136 ms 23664 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 3 ms 2900 KB Output is correct
6 Correct 16 ms 4368 KB Output is correct
7 Correct 211 ms 19644 KB Output is correct
8 Correct 213 ms 24240 KB Output is correct
9 Correct 116 ms 19860 KB Output is correct
10 Correct 131 ms 19124 KB Output is correct
11 Correct 112 ms 21880 KB Output is correct
12 Correct 121 ms 21936 KB Output is correct
13 Correct 129 ms 23692 KB Output is correct