#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;
int sz;
pair<int,int> q[500005];
pair<int,int> ans2[500005];
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);
return;
}
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);
}
inline void add(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;
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));
// cout<<">"<<l2<<" "<<r1<<'\n';
update(1,sz,l2,r1,1,l2,r1);
}
inline void del(int x) {
set<pair<int,int> > ::iterator q1;
q1=s.upper_bound(make_pair(x,0));
--q1;
int l1=q1->first;
int r1=q1->second;
s.erase(q1);
s.insert(make_pair(l1,x));
s.insert(make_pair(x+1,r1));
}
inline void push(int x) {
q[x+x].first=min(q[x+x].first,q[x].first);
q[x+x].second=max(q[x+x].second,q[x].second);
q[x+x+1].first=min(q[x+x+1].first,q[x].first);
q[x+x+1].second=max(q[x+x+1].second,q[x].second);
}
inline void solve() {
sz=1;
while (sz<n) sz+=sz;
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,q[sz+i-1].first);
ans2[i].second=max(i,q[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:49:9: warning: unused variable 'l1' [-Wunused-variable]
int l1=q1->first;
^~
synchronization.cpp:55:9: warning: unused variable 'r2' [-Wunused-variable]
int r2=q1->second;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
9848 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
16980 KB |
Output is correct |
| 2 |
Correct |
77 ms |
16980 KB |
Output is correct |
| 3 |
Correct |
147 ms |
21936 KB |
Output is correct |
| 4 |
Correct |
156 ms |
22012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
22012 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
263 ms |
32616 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
32616 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
32616 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
