#include <bits/stdc++.h>
using namespace std;
int n,m,qq;
int ans;
vector<pair<int,int> > v[200005];
int f[200005];
int last[200005];
int c[200005];
int x,y;
void dfs(int x,int y,int xx,int yy) {
if (xx<=yy) ++ans;
for (int i=0;i<v[x].size();++i) {
int to=v[x][i].first;
if (to==y) continue;
int xx2;
int yy2=min(yy,last[v[x][i].second]);
xx2=f[v[x][i].second];
dfs(to,x,xx2,yy2);
}
}
set<pair<int,int> > s;
pair<int,int> q[500005];
pair<int,int> t[500005];
int sz;
pair<int,int> ans2[500005];
inline void push(int x) {
q[x+x].first=min(q[x+x].first,q[x].first);
q[x+x+1].first=min(q[x+x+1].first,q[x].first);
t[x+x].first=min(t[x+x].first,q[x].first);
t[x+x+1].first=min(t[x+x+1].first,q[x].first);
q[x+x].second=max(q[x+x].second,q[x].second);
q[x+x+1].second=max(q[x+x+1].second,q[x].second);
t[x+x].second=max(t[x+x].second,q[x].second);
t[x+x+1].second=max(t[x+x+1].second,q[x].second);
}
void update(int l,int r,int ll,int rr,int x,int y,int z) {
if (l>r || ll>r || l>rr || ll>rr) return;
if (l>=ll && r<=rr) {
q[x].first=min(q[x].first,y);
q[x].second=max(q[x].second,z);
t[x].first=min(t[x].first,y);
t[x].second=max(t[x].second,z);
return;
}
push(x);
int mid=(l+r)>>1;
update(l,mid,ll,rr,x+x,y,z);
update(mid+1,r,ll,rr,x+x+1,y,z);
t[x].first=min(t[x+x].first,t[x+x+1].first);
t[x].second=max(t[x+x].second,t[x+x+1].second);
}
pair<int,int> get(int l,int r,int ll,int rr,int x) {
if (l>r || l>rr || ll>r || ll>rr) return make_pair(1e9,-1e9);
if (l>=ll && r<=rr) return t[x];
push(x);
int mid=(l+r)>>1;
pair<int,int> res=get(l,mid,ll,rr,x+x);
pair<int,int> res2=get(mid+1,r,ll,rr,x+x+1);
res.first=min(res.first,res2.first);
res.second=max(res.second,res2.second);
return res;
}
inline void add(int x) {
set<pair<int,int> > ::iterator q1;
q1=s.lower_bound(make_pair(x+1,0));
int l1=q1->first;
int r1=q1->second;
s.erase(q1);
q1=s.lower_bound(make_pair(x+1,0));
--q1;
int l2=q1->first;
int r2=q1->second;
s.erase(q1);
s.insert(make_pair(l2,r1));
pair<int,int> res=get(1,sz,l2,r1,1);
// cout<<l2<<" "<<r1<<" "<<res.first<<" "<<res.second<<'\n';
update(1,sz,l2,r1,1,res.first,res.second);
}
inline void del(int x) {
set<pair<int,int> > ::iterator q1;
q1=s.lower_bound(make_pair(x+1,0));
--q1;
int l1=q1->first;
int r1=q1->second;
// cout<<x<<" "<<l1<<" "<<r1<<'\n';
s.erase(q1);
s.insert(make_pair(l1,x));
s.insert(make_pair(x+1,r1));
}
inline void solve() {
sz=1;
while (sz<n) sz+=sz;
for (int i=1;i<=n;++i)
t[sz+i-1]=make_pair(i,i);
for (int i=sz-1;i>0;--i) {
t[i].first=t[i+i].first;
t[i].second=t[i+i].second;
}
for (int i=1;i<=sz+sz;++i)
q[i]=make_pair(1e9,-1e9);
for (int i=1;i<=n;++i)
s.insert(make_pair(i,i));
for (int i=1;i<=m;++i) {
cin>>x;
c[x]^=1;
if (c[x]) add(x);
else del(x);
}
for (int i=1;i<sz;++i)
push(i);
for (int i=1;i<=n;++i) {
ans2[i].first=min(i,t[sz+i-1].first);
ans2[i].second=max(i,t[sz+i-1].second);
}
while (qq--) {
cin>>x;
cout<<ans2[x].second-ans2[x].first+1<<'\n';
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m>>qq;
bool t=false;
for (int i=1;i<n;++i) {
cin>>x>>y;
if (x!=i || y!=i+1) t=true;
v[x].push_back(make_pair(y,i));
v[y].push_back(make_pair(x,i));
f[i]=m+2;
last[i]=m+1;
}
if (t==false) {
solve();
return 0;
}
for (int i=1;i<=m;++i) {
cin>>x;
c[x]^=1;
if (c[x]) {
f[x]=min(f[x],i);
} else last[x]=i;
}
for (int i=1;i<n;++i) {
if (c[i]) last[i]=m+1;
}
for (int i=1;i<=qq;++i) {
cin>>x;
ans=0;
dfs(x,-1,0,1e9);
cout<<ans<<'\n';
}
}
Compilation message
synchronization.cpp: In function 'void dfs(int, int, int, int)':
synchronization.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[x].size();++i) {
~^~~~~~~~~~~~
synchronization.cpp: In function 'void add(int)':
synchronization.cpp:77:9: warning: unused variable 'l1' [-Wunused-variable]
int l1=q1->first;
^~
synchronization.cpp:83:9: warning: unused variable 'r2' [-Wunused-variable]
int r2=q1->second;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
4984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
12256 KB |
Output is correct |
| 2 |
Correct |
55 ms |
12256 KB |
Output is correct |
| 3 |
Correct |
219 ms |
19204 KB |
Output is correct |
| 4 |
Correct |
228 ms |
19204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
19204 KB |
Output is correct |
| 2 |
Correct |
6 ms |
19204 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
19204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
447 ms |
19432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
19432 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
19432 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
