oj.uz

Submission #895710

# Submission time Handle Problem Language Result Execution time Memory
895710 2023-12-30T15:15:28 Z imarn Synchronization (JOI13_synchronization) C++14
100 / 100
 207 ms 24148 KB 
#include<bits/stdc++.h>
#define ld long double
#define pii pair<long long,int>
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define pb push_back
#define f first
#define s second
#define vi vector<ll>
#define vvi vector<vi>
#define vpii vector<pii>
#define ll long long
using namespace std;
const int N=1e5+5;
vector<int>g[N];
vpii edge(N);
int fw[N]{0},pr[N][18]{0},tin[N],tout[N],t=0,d[N]{0},dd[N]{0};
bool vis[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 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;
}
void dfs(int u,int p){
    pr[u][0]=p;tin[u]=++t;
    for(int i=1;i<=17;i++)pr[u][i]=pr[pr[u][i-1]][i-1];
    for(auto v:g[u]){
        if(v==p)continue;
        dfs(v,u);
    }tout[u]=t;
}
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>>edge[i].f>>edge[i].s;
        g[edge[i].f].pb(edge[i].s);
        g[edge[i].s].pb(edge[i].f);
    }dfs(1,1);
    for(int i=1;i<=n;i++)add(tin[i],1),add(tout[i]+1,-1),d[i]=1;
    while(m--){
        int x;cin>>x;
        int u=edge[x].f,v=edge[x].s;
        if(v==pr[u][0])swap(u,v);
        if(!vis[x]){
            d[get(u)]+=d[v]-dd[v];vis[x]=1;
            add(tin[v],-1);add(tout[v]+1,1);
        }
        else {
            d[v]=dd[v]=d[get(u)];vis[x]=0;
            add(tin[v],1);add(tout[v]+1,-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 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5040 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct
6 Correct 2 ms 5208 KB Output is correct
7 Correct 12 ms 8284 KB Output is correct
8 Correct 12 ms 8284 KB Output is correct
9 Correct 14 ms 8192 KB Output is correct
10 Correct 140 ms 18780 KB Output is correct
11 Correct 119 ms 18760 KB Output is correct
12 Correct 145 ms 23380 KB Output is correct
13 Correct 73 ms 18888 KB Output is correct
14 Correct 81 ms 18000 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 18752 KB Output is correct
2 Correct 73 ms 18772 KB Output is correct
3 Correct 71 ms 20860 KB Output is correct
4 Correct 75 ms 20816 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 16 ms 8688 KB Output is correct
8 Correct 207 ms 21292 KB Output is correct
9 Correct 189 ms 21428 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 21332 KB Output is correct
2 Correct 110 ms 21332 KB Output is correct
3 Correct 111 ms 21328 KB Output is correct
4 Correct 114 ms 21580 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 2 ms 4984 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 14 ms 8280 KB Output is correct
7 Correct 168 ms 19800 KB Output is correct
8 Correct 192 ms 24148 KB Output is correct
9 Correct 97 ms 19912 KB Output is correct
10 Correct 110 ms 19280 KB Output is correct
11 Correct 99 ms 21956 KB Output is correct
12 Correct 100 ms 21844 KB Output is correct
13 Correct 115 ms 23756 KB Output is correct