oj.uz

Submission #844207

# Submission time Handle Problem Language Result Execution time Memory
844207 2023-09-05T11:27:29 Z winter0101 Synchronization (JOI13_synchronization) C++14
100 / 100
 199 ms 28380 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=1e5+9;
int n,m,q;
vector<int>a[maxn];
int st[maxn][21],bit[maxn],val[maxn],last[maxn],dep[maxn],in[maxn],out[maxn],tme=0;
pii edg[maxn];
bool active[maxn];
void dfs(int u,int par){
val[u]=1;
in[u]=++tme;
for(auto v:a[u]){
    if (v==par)continue;
    st[v][0]=u;
    dep[v]=dep[u]+1;
    for1(j,1,20){
    st[v][j]=st[st[v][j-1]][j-1];
    }
    dfs(v,u);
}
out[u]=tme;
}
void add(int pos,int v){
for(;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]+=v;
}
int get(int pos){
int sum=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
int root(int u){
for2(i,20,0){
if (!st[u][i])continue;
if (get(in[u])-get(in[st[u][i]])==dep[u]-dep[st[u][i]]){
u=st[u][i];
}
}
return u;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>m>>q;
    for1(i,1,n-1){
    int u,v;
    cin>>u>>v;
    a[u].pb(v);
    a[v].pb(u);
    edg[i]={u,v};
    }
    dfs(1,0);
    for1(i,1,m){
    int x;
    cin>>x;
    int u=edg[x].fi,v=edg[x].se;
    if (st[u][0]==v)swap(u,v);
    if (active[x]){
        last[v]=val[v]=val[root(u)];
        add(in[v],-1);
        add(out[v]+1,1);
    }
    else {
        val[root(u)]+=val[v]-last[v];
        add(in[v],1);
        add(out[v]+1,-1);
    }
    active[x]^=1;
    }
    for1(i,1,q){
    int k;
    cin>>k;
    cout<<val[root(k)]<<'\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 1 ms 5720 KB Output is correct
3 Correct 2 ms 5976 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5720 KB Output is correct
6 Correct 3 ms 6132 KB Output is correct
7 Correct 11 ms 6488 KB Output is correct
8 Correct 9 ms 6640 KB Output is correct
9 Correct 9 ms 6488 KB Output is correct
10 Correct 106 ms 19536 KB Output is correct
11 Correct 109 ms 19536 KB Output is correct
12 Correct 156 ms 27468 KB Output is correct
13 Correct 54 ms 19492 KB Output is correct
14 Correct 75 ms 17468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 23632 KB Output is correct
2 Correct 60 ms 21336 KB Output is correct
3 Correct 75 ms 25060 KB Output is correct
4 Correct 75 ms 25168 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 KB Output is correct
2 Correct 1 ms 5720 KB Output is correct
3 Correct 1 ms 5720 KB Output is correct
4 Correct 2 ms 5724 KB Output is correct
5 Correct 1 ms 5720 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 14 ms 7256 KB Output is correct
8 Correct 193 ms 28244 KB Output is correct
9 Correct 192 ms 28240 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 28380 KB Output is correct
2 Correct 120 ms 27812 KB Output is correct
3 Correct 118 ms 27984 KB Output is correct
4 Correct 117 ms 27936 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 KB Output is correct
2 Correct 1 ms 5720 KB Output is correct
3 Correct 2 ms 5720 KB Output is correct
4 Correct 1 ms 5720 KB Output is correct
5 Correct 2 ms 5720 KB Output is correct
6 Correct 12 ms 6704 KB Output is correct
7 Correct 139 ms 20560 KB Output is correct
8 Correct 193 ms 25168 KB Output is correct
9 Correct 67 ms 18120 KB Output is correct
10 Correct 95 ms 18004 KB Output is correct
11 Correct 81 ms 21840 KB Output is correct
12 Correct 82 ms 21840 KB Output is correct
13 Correct 121 ms 25648 KB Output is correct