Submission #52596

#TimeUsernameProblemLanguageResultExecution timeMemory
52596SmelskiySynchronization (JOI13_synchronization)C++14
100 / 100
275 ms15220 KiB
#include <bits/stdc++.h>
using namespace std;




int timer;
int x,y,xx,yy;
int n,m,qq;
int tin[100005];
int tout[100005];
vector<int> v[100005];
int sz;
int res[100005];
int last[100005];
pair<int,int> a[100005];
int cnt[200005];
int t[600006];
int poc[600006];

void dfs(int x,int y) {
    tin[x]=++timer;
    poc[timer]=x;
    for (int i=0;i<v[x].size();++i) {
        int to=v[x][i];
        if (to!=y) dfs(to,x);
    }
    tout[x]=timer;
}

int get(int l,int r,int x,int y) {
    if (t[x]<y || l>y) return -1;
    if (l==r) return poc[l];
    int mid=(l+r)>>1;
    int res=get(mid+1,r,x+x+1,y);
    if (res!=-1) return res;
    return get(l,mid,x+x,y);
}

void update(int x,int y) {
    x+=sz-1;
    t[x]=y;
    x>>=1;
    while (x) {
        t[x]=max(t[x+x],t[x+x+1]);
        x>>=1;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m>>qq;
    for (int i=1;i<n;++i) {
        cin>>x>>y;
        a[i]=make_pair(x,y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    for (int i=1;i<n;++i) {
        x=a[i].first;
        y=a[i].second;
        if (tin[x]>tin[y]) swap(a[i].first,a[i].second);
    }
    sz=1;
    while (sz<n) sz+=sz;
    for (int i=1;i<=n;++i)
        t[sz+i-1]=tout[poc[i]];
    for (int i=sz-1;i>0;--i)
        t[i]=max(t[i+i],t[i+i+1]);
    for (int i=1;i<=n;++i) {
        res[i]=1;
    }
    for (int i=1;i<=m;++i) {
        cin>>xx;
        x=a[xx].first;
        y=a[xx].second;
        yy=get(1,sz,1,tin[x]);
        cnt[xx]^=1;
        if (cnt[xx]) {
            res[yy]+=res[y]-last[y];
            update(tin[y],0);
        } else {
            res[y]=last[y]=res[yy];
            update(tin[y],tout[y]);
        }
    }
    while (qq--) {
        cin>>x;
        x=get(1,sz,1,tin[x]);
        cout<<res[x]<<'\n';
    }

}

Compilation message (stderr)

synchronization.cpp: In function 'void dfs(int, int)':
synchronization.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();++i) {
                  ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...