oj.uz

Submission #882197

# Submission time Handle Problem Language Result Execution time Memory
882197 2023-12-02T19:18:27 Z abcvuitunggio Synchronization (JOI13_synchronization) C++17
100 / 100
 276 ms 36372 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,q,x[100001],y[100001],d,c,last[100001],s[100001],res[100001],tin[100001],tout[100001],t,p[100001][20],ft[100001][2];
vector <int> ke[100001];
void update(int i, int j, int val){
    for (;i<=n;i+=i&(-i))
        ft[i][j]+=val;
}
int get(int i, int j){
    int res=0;
    for (;i;i-=i&(-i))
        res+=ft[i][j];
    return res;
}
int get(int u){
    return get(tout[u],1)-get(tin[u]-1,1);
}
void dfs(int u, int par){
    tin[u]=++t;
    for (int v:ke[u])
        if (v!=par){
            p[v][0]=u;
            for (int i=1;i<20;i++)
                p[v][i]=p[p[v][i-1]][i-1];
            dfs(v,u);
        }
    tout[u]=t;
}
int f(int u){
    for (int i=19;i>=0;i--)
        if (p[u][i]&&get(tin[u],0)-get(tin[p[u][i]],0)==(1<<i))
            u=p[u][i];
    return u;
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> m >> q;
    for (int i=1;i<n;i++){
        cin >> x[i] >> y[i];
        ke[x[i]].push_back(y[i]);
        ke[y[i]].push_back(x[i]);
    }
    fill(res,res+n+1,1);
    dfs(1,1);
    for (int i=1;i<=n;i++){
        update(tin[i],1,1);
        if (i>1)
            update(tin[p[i][0]],1,-1);
    }
    for (int i=1;i<n;i++)
        if (x[i]==p[y[i]][0])
            swap(x[i],y[i]);
    while (m--){
        cin >> d;
        s[d]^=1;
        update(tin[x[d]],0,s[d]*2-1);
        update(tout[x[d]]+1,0,1-s[d]*2);
        int u=f(y[d]);
        if (s[d]){
            int val=get(x[d])-last[d];
            update(tin[y[d]],1,val);
            if (u!=1)
                update(tin[p[u][0]],1,-val);
            res[u]+=val;
            continue;
        }
        last[d]=get(x[d]);
        res[x[d]]=res[u];
    }
    while (q--){
        cin >> c;
        cout << res[f(c)] << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 11 ms 11612 KB Output is correct
8 Correct 11 ms 11608 KB Output is correct
9 Correct 11 ms 11412 KB Output is correct
10 Correct 174 ms 31292 KB Output is correct
11 Correct 162 ms 31516 KB Output is correct
12 Correct 211 ms 35680 KB Output is correct
13 Correct 84 ms 31196 KB Output is correct
14 Correct 105 ms 30804 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 32484 KB Output is correct
2 Correct 81 ms 32280 KB Output is correct
3 Correct 99 ms 34132 KB Output is correct
4 Correct 98 ms 34268 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8840 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 1 ms 8844 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 18 ms 12124 KB Output is correct
8 Correct 255 ms 35156 KB Output is correct
9 Correct 246 ms 35156 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 35136 KB Output is correct
2 Correct 148 ms 34808 KB Output is correct
3 Correct 136 ms 35156 KB Output is correct
4 Correct 153 ms 35072 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 13 ms 11612 KB Output is correct
7 Correct 184 ms 32432 KB Output is correct
8 Correct 276 ms 36372 KB Output is correct
9 Correct 94 ms 32456 KB Output is correct
10 Correct 127 ms 32084 KB Output is correct
11 Correct 107 ms 34512 KB Output is correct
12 Correct 99 ms 34360 KB Output is correct
13 Correct 147 ms 36092 KB Output is correct