#include <bits/stdc++.h>
#define a first
#define b second
using namespace std;
typedef pair<int,int> pii;
struct idxtree {
int tree[270000];
int key = 131072, type;
idxtree(int t) {
type = t;
int ival = ((t)?987654321:-987654321);
for (int i=0;i<key*2;i++) tree[i] = ival;
}
int mer(int a, int b) {
if (type) return min(a,b);
return max(a,b);
}
void upd(int s, int e, int val) {
s += key; e += key;
while(s<=e) {
if (s&1) tree[s] = mer(tree[s],val);
if (~e&1) tree[e] = mer(tree[e],val);
s = (s+1)>>1; e = (e-1)>>1;
}
}
int getv(int idx) {
idx += key;
int res = ((type)?987654321:-987654321);
while(idx>0) {
res = mer(res,tree[idx]);
idx>>=1;
}
return res;
}
} maxt(0), mint(1);
int n, m, q;
vector<int> lis[100100];
vector<int> id[100100];
pii edg[100100];
int cha[200100];
int que[100100];
int last[100100];
bool on[100100];
vector<pii> ran[100100];
bool visit[100100];
void dfs(int here, int p, int tim) {
int i;
visit[here] = true;
for (i=0;i<lis[here].size();i++) {
int there = lis[here][i];
int idx = id[here][i];
if (there==p) continue;
int nim = lower_bound(ran[idx].begin(),ran[idx].end(),pii(tim,m+10))-ran[idx].begin()-1;
if (nim<0) continue;
dfs(there,here,min(tim,ran[idx][nim].second));
}
}
set<pii> se;
int main() {
int i;
//freopen("input","r",stdin);
bool flag = true;
scanf("%d%d%d",&n,&m,&q);
for (i=0;i<n-1;i++) {
int a, b;
scanf("%d%d",&a,&b);
a--;b--;
if (a!=i||b!=i+1) flag = false;
lis[a].push_back(b);
lis[b].push_back(a);
id[a].push_back(i);
id[b].push_back(i);
edg[i] = pii(a,b);
}
for (i=0;i<m;i++) {
scanf("%d",&cha[i]);
cha[i]--;
if (on[cha[i]]) ran[cha[i]].push_back(pii(last[cha[i]],i));
on[cha[i]] = !on[cha[i]];
last[cha[i]] = i;
}
for (i=0;i<n-1;i++) if (on[i]) ran[i].push_back(pii(last[i],m));
for (i=0;i<q;i++) {
scanf("%d",&que[i]);
que[i]--;
}
if (q==1) {
dfs(que[i],-1,m);
int cnt = 0;
for (int j=0;j<n;j++) if (visit[j]) cnt++;
printf("%d\n",cnt);
}
else if (flag) {
for (i=0;i<n;i++) maxt.upd(i,i,i);
for (i=0;i<n;i++) mint.upd(i,i,i);
for (i=0;i<n;i++) se.insert(pii(i,i));
for (i=0;i<n-1;i++) on[i] = false;
for (i=0;i<m;i++) {
if (on[cha[i]]) {
set<pii>::iterator it = --se.lower_bound(pii(cha[i],m+10));
pii tmp = (*it);
se.erase(it);
se.insert(pii(tmp.first,cha[i]));
se.insert(pii(cha[i]+1,tmp.second));
}
else {
set<pii>::iterator it = se.lower_bound(pii(cha[i],m+10));
set<pii>::iterator pt = --it; ++it;
mint.upd(it->first,it->second,mint.getv(cha[i]));
maxt.upd(pt->first,pt->second,maxt.getv(cha[i]+1));
pii tmp = pii(pt->first,it->second);
se.erase(it); se.erase(pt);
se.insert(tmp);
}
on[cha[i]] = !on[cha[i]];
}
for (i=0;i<q;i++) {
printf("%d\n",maxt.getv(que[i])-mint.getv(que[i])+1);
}
}
return 0;
}
Compilation message
synchronization.cpp:11:15: warning: non-static data member initializers only available with -std=c++11 or -std=gnu++11
int key = 131072, type;
^
synchronization.cpp: In function 'void dfs(int, int, int)':
synchronization.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<lis[here].size();i++) {
^
synchronization.cpp: In function 'int main()':
synchronization.cpp:72:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&n,&m,&q);
^
synchronization.cpp:75:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
^
synchronization.cpp:85:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&cha[i]);
^
synchronization.cpp:93:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&que[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
13716 KB |
Output is correct |
| 2 |
Correct |
0 ms |
13716 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
13716 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
27908 KB |
Output is correct |
| 2 |
Correct |
113 ms |
27776 KB |
Output is correct |
| 3 |
Incorrect |
76 ms |
23088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
13716 KB |
Output is correct |
| 2 |
Correct |
6 ms |
13716 KB |
Output is correct |
| 3 |
Correct |
6 ms |
13716 KB |
Output is correct |
| 4 |
Correct |
3 ms |
13716 KB |
Output is correct |
| 5 |
Correct |
0 ms |
13716 KB |
Output is correct |
| 6 |
Correct |
3 ms |
13848 KB |
Output is correct |
| 7 |
Correct |
23 ms |
15168 KB |
Output is correct |
| 8 |
Correct |
376 ms |
27444 KB |
Output is correct |
| 9 |
Correct |
446 ms |
27444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
443 ms |
27444 KB |
Output is correct |
| 2 |
Correct |
193 ms |
27708 KB |
Output is correct |
| 3 |
Correct |
143 ms |
27840 KB |
Output is correct |
| 4 |
Correct |
163 ms |
27840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
13716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
