This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |