oj.uz

Submission #636872

# Submission time Handle Problem Language Result Execution time Memory
636872 2022-08-30T10:53:01 Z Cross_Ratio Synchronization (JOI13_synchronization) C++14
100 / 100
 1215 ms 25792 KB 
#include <bits/stdc++.h>
using namespace std;
int DP1[200005];
int DP2[200005];
int par[200005][22];
int in[200005];
int out[200005];
int global_ETT = 0;
vector<vector<int>> adj;
void dfs(int c, int p) {
    in[c] = global_ETT;
    global_ETT++;
    par[c][0] = p;
    for(int n : adj[c]) {
        if(n==p) continue;
        dfs(n, c);
    }
    out[c] = global_ETT;
}
struct SegTree {
    vector<int> seg;
    int MAX;
    void init(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    void update(int n) {
        n += MAX/2;
        n /= 2;
        while(n) {
            seg[n] = seg[2*n] + seg[2*n+1];
            n /= 2;
        }
    }
    void Edit(int n, int a) {
        seg[n+MAX/2] += a;
        update(n);
    }
    int sum(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return sum(s, e, 2*n, ns, mid) + sum(s, e, 2*n+1, mid, ne);
    }
};
array<int, 2> Edge[200005];
SegTree tree;
int Top(int n) {
    for(int i = 19; i >= 0; i--) {
        int n2 = par[n][i];
        if(n2 != -1 && tree.sum(0, in[n]+1, 1, 0, tree.MAX/2) == tree.sum(0, in[n2]+1, 1, 0, tree.MAX/2)) {
            n = n2;
        }
    }
    return n;
}
bool type[200005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M, Q;
    cin >> N >> M >> Q;
    adj.resize(N);
    int i, j;
    tree.init(N+5);
    for(i=0;i<N-1;i++) {
        cin >> Edge[i][0] >> Edge[i][1];
        Edge[i][0]--;
        Edge[i][1]--;
        adj[Edge[i][0]].push_back(Edge[i][1]);
        adj[Edge[i][1]].push_back(Edge[i][0]);
    }
    for(i=0;i<N;i++) DP1[i] = 1;
    dfs(0, -1);
    for(i=1;i<20;i++) {
        for(j=0;j<N;j++) {
            if(par[j][i-1]!=-1) {
                par[j][i] = par[par[j][i-1]][i-1];
            }
        }
    }
    for(i=0;i<N;i++) {
        tree.Edit(in[i], 1);
        tree.Edit(out[i], -1);
    }
    while(M--) {
        int x;
        cin >> x;
        x--;
        int u = Edge[x][0], v = Edge[x][1];
        if(par[u][0]==v) swap(u, v);
        int c = Top(u);
        if(type[x]) {
            DP1[v] = DP1[c];
            DP2[v] = DP1[c];
            tree.Edit(in[v], 1);
            tree.Edit(out[v], -1);
            type[x] = false;
        }
        else {
            DP1[c] += DP1[v] - DP2[v];
            tree.Edit(in[v], -1);
            tree.Edit(out[v], 1);
            type[x] = true;
        }
    }
    while(Q--) {
        int x;
        cin >> x;
        x--;
        cout << DP1[Top(x)] << '\n';
    }
}

Compilation message

synchronization.cpp: In member function 'int SegTree::sum(int, int, int, int, int)':
synchronization.cpp:44:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 548 KB Output is correct
7 Correct 63 ms 2260 KB Output is correct
8 Correct 65 ms 2360 KB Output is correct
9 Correct 60 ms 2260 KB Output is correct
10 Correct 789 ms 20496 KB Output is correct
11 Correct 803 ms 20444 KB Output is correct
12 Correct 909 ms 25020 KB Output is correct
13 Correct 649 ms 20208 KB Output is correct
14 Correct 430 ms 19352 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 22332 KB Output is correct
2 Correct 630 ms 21812 KB Output is correct
3 Correct 397 ms 23956 KB Output is correct
4 Correct 392 ms 23884 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 596 KB Output is correct
7 Correct 96 ms 2904 KB Output is correct
8 Correct 1213 ms 25660 KB Output is correct
9 Correct 1212 ms 25748 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1215 ms 25792 KB Output is correct
2 Correct 719 ms 25024 KB Output is correct
3 Correct 723 ms 25288 KB Output is correct
4 Correct 716 ms 25128 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 7 ms 468 KB Output is correct
6 Correct 95 ms 2412 KB Output is correct
7 Correct 1131 ms 21108 KB Output is correct
8 Correct 1213 ms 25732 KB Output is correct
9 Correct 938 ms 21332 KB Output is correct
10 Correct 723 ms 20568 KB Output is correct
11 Correct 908 ms 23508 KB Output is correct
12 Correct 913 ms 23372 KB Output is correct
13 Correct 720 ms 25352 KB Output is correct