oj.uz

Submission #885268

# Submission time Handle Problem Language Result Execution time Memory
885268 2023-12-09T11:49:47 Z imarn Synchronization (JOI13_synchronization) C++14
100 / 100
 299 ms 32428 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
using namespace std;
const int N=2e5+5;
vector<int>g[N];
ll fw[N]{0};
pii e[N];
bool ee[N]{0};
int d[N]{0},dd[N]{0};
int pr[N][18]{0},tin[N]{0},tout[N]{0};
void add(int i,int amt){
    for(;i<N;i+=i&-i)fw[i]+=amt;
}
int qr(int i,int res=0){
    for(;i;i-=i&-i)res+=fw[i];
    return res;
}int t=0;
void dfs(int u,int p){
    pr[u][0]=p;d[u]=1;
    for(int i=1;i<=17;i++)pr[u][i]=pr[pr[u][i-1]][i-1];
    tin[u]=++t;
    for(auto v:g[u])if(v!=p)dfs(v,u);
    tout[u]=++t;
}
int get(int u){
    int x=qr(tin[u]);
    for(int i=17;i>=0;i--)if(qr(tin[pr[u][i]])==x)u=pr[u][i];
    return u;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m,q;cin>>n>>m>>q;
    for(int i=1;i<=n-1;i++)cin>>e[i].f>>e[i].s,g[e[i].f].pb(e[i].s),g[e[i].s].pb(e[i].f);
    dfs(1,1);for(int i=1;i<=n;i++)add(tin[i],-1),add(tout[i],1);
    while(m--){
        int x;cin>>x;
        int u=e[x].f,v=e[x].s;
        if(tin[u]>tin[v])swap(u,v);
        if(ee[x]){
            d[v]=dd[v]=d[get(u)];
            add(tin[v],-1);
            add(tout[v],1);ee[x]=0;
        }else {
            d[get(u)]+=d[v]-dd[v];
            add(tin[v],1);
            add(tout[v],-1);ee[x]=1;
        }
    }
    while(q--){
        int x;cin>>x;cout<<d[get(x)]<<"\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13148 KB Output is correct
2 Correct 2 ms 13204 KB Output is correct
3 Correct 2 ms 13196 KB Output is correct
4 Correct 2 ms 13400 KB Output is correct
5 Correct 2 ms 13148 KB Output is correct
6 Correct 3 ms 13404 KB Output is correct
7 Correct 12 ms 15956 KB Output is correct
8 Correct 13 ms 15816 KB Output is correct
9 Correct 12 ms 15760 KB Output is correct
10 Correct 146 ms 27252 KB Output is correct
11 Correct 151 ms 26992 KB Output is correct
12 Correct 179 ms 31716 KB Output is correct
13 Correct 86 ms 26896 KB Output is correct
14 Correct 95 ms 26352 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 29196 KB Output is correct
2 Correct 88 ms 29032 KB Output is correct
3 Correct 84 ms 31136 KB Output is correct
4 Correct 94 ms 31032 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13152 KB Output is correct
2 Correct 3 ms 13212 KB Output is correct
3 Correct 2 ms 13148 KB Output is correct
4 Correct 2 ms 13148 KB Output is correct
5 Correct 2 ms 13200 KB Output is correct
6 Correct 4 ms 13148 KB Output is correct
7 Correct 17 ms 16280 KB Output is correct
8 Correct 214 ms 32296 KB Output is correct
9 Correct 220 ms 32428 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 32332 KB Output is correct
2 Correct 122 ms 32148 KB Output is correct
3 Correct 132 ms 32092 KB Output is correct
4 Correct 129 ms 32072 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13148 KB Output is correct
2 Correct 3 ms 12988 KB Output is correct
3 Correct 2 ms 13148 KB Output is correct
4 Correct 2 ms 13148 KB Output is correct
5 Correct 4 ms 13240 KB Output is correct
6 Correct 16 ms 15888 KB Output is correct
7 Correct 229 ms 27748 KB Output is correct
8 Correct 299 ms 32340 KB Output is correct
9 Correct 100 ms 28048 KB Output is correct
10 Correct 117 ms 27620 KB Output is correct
11 Correct 114 ms 30356 KB Output is correct
12 Correct 108 ms 30296 KB Output is correct
13 Correct 133 ms 32340 KB Output is correct