oj.uz

Submission #669068

# Submission time Handle Problem Language Result Execution time Memory
669068 2022-12-05T13:50:30 Z zaneyu Synchronization (JOI13_synchronization) C++14
100 / 100
 260 ms 27396 KB 
/*input
5 6 3
1 2
1 3
2 4
2 5
1
2
1
4
4
3
1
4
5
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace __gnu_pbds;
typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<ll,ll>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET(v,x) lower_bound(ALL(v),x)-v.begin()
const int maxn=2e5+5;
const ll INF=0x3f3f3f3f;
const ld PI=acos(-1.0l);
const ld eps=1e-6;
const ll INF64=4e18+1;
const int MOD=1e9+7;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?"\n":"");
    return out;
}
vector<int> v[maxn];
int par[maxn][20],in[maxn],out[maxn];
int cur=1;
bool on[maxn];
int ans[maxn],pv[maxn];
void dfs(int u,int p){
    par[u][0]=p;
    in[u]=(cur++);
    for(int x:v[u]){
        if(x==p) continue;
        dfs(x,u);
    }
    out[u]=cur;
}
int bit[maxn];
void upd(int x,int v){
    while(x<maxn){
        bit[x]+=v;
        x+=lowb(x);
    }
}
int query(int x){
    int ans=0;
    while(x){
        ans+=bit[x];
        x-=lowb(x);
    }
    return ans;
}
int get(int x){
    int z=query(in[x]);
    for(int j=19;j>=0;j--){
        int b=par[x][j];
        if(b!=-1 and query(in[b])==z) x=b;
    }
    return x;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    vector<pii> ed;
    REP(i,n-1){
        int a,b;
        cin>>a>>b;
        --a,--b;
        v[a].pb(b),v[b].pb(a);
        ed.pb({a,b});
    }
    dfs(0,-1);
    REP1(j,19){
        REP(i,n){
            if(par[i][j-1]!=-1) par[i][j]=par[par[i][j-1]][j-1];
            else par[i][j]=-1;
        }
    }
    for(auto &x:ed) if(par[x.f][0]==x.s) swap(x.f,x.s);
    REP(i,n) upd(in[i],-1),upd(out[i],1),ans[i]=1;
    
    REP(i,m){
        int x;
        cin>>x;
        --x;
        int a=ed[x].f,b=ed[x].s;
        assert(par[b][0]==a);
        if(on[x]){
            ans[b]=pv[b]=ans[get(a)];
            upd(in[b],-1),upd(out[b],1);
        }   
        else{
            ans[get(a)]+=ans[b]-pv[b];
            upd(in[b],1),upd(out[b],-1);
        }
        on[x]^=1;
    }
    while(q--){
        int x;
        cin>>x;
        --x;
        cout<<ans[get(x)]<<'\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5024 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5204 KB Output is correct
7 Correct 12 ms 6736 KB Output is correct
8 Correct 12 ms 6736 KB Output is correct
9 Correct 12 ms 6736 KB Output is correct
10 Correct 164 ms 22040 KB Output is correct
11 Correct 155 ms 22048 KB Output is correct
12 Correct 207 ms 26620 KB Output is correct
13 Correct 98 ms 21948 KB Output is correct
14 Correct 105 ms 20996 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 23852 KB Output is correct
2 Correct 89 ms 23656 KB Output is correct
3 Correct 92 ms 25708 KB Output is correct
4 Correct 91 ms 25784 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 4 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5028 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 18 ms 7248 KB Output is correct
8 Correct 252 ms 27392 KB Output is correct
9 Correct 260 ms 27392 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 27396 KB Output is correct
2 Correct 149 ms 26804 KB Output is correct
3 Correct 150 ms 26900 KB Output is correct
4 Correct 152 ms 26892 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5048 KB Output is correct
5 Correct 4 ms 5160 KB Output is correct
6 Correct 15 ms 6796 KB Output is correct
7 Correct 199 ms 22816 KB Output is correct
8 Correct 252 ms 27396 KB Output is correct
9 Correct 122 ms 23156 KB Output is correct
10 Correct 139 ms 22308 KB Output is correct
11 Correct 113 ms 25040 KB Output is correct
12 Correct 120 ms 25044 KB Output is correct
13 Correct 139 ms 26868 KB Output is correct