#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 100;
int sz = 16;
vector<int> lzR(2*sz, -1), lzL(2*sz, 1e9), valsR(2*sz, -1), valsL(2*sz, 1e9);
void upd(int i, int l, int r, int x, int y, int valR, int valL) {
if (y < x) return;
valR = max(valR, lzR[i]);
valL = min(valL, lzL[i]);
if (x == l && y == r) {
lzR[i] = max(lzR[i], valR);
lzL[i] = min(lzL[i], valL);
valsR[i] = max(valsR[i], valR);
valsL[i] = min(valsL[i], valL);
return;
}
int mid = (l+r)/2;
upd(2*i, l, mid, x, min(y,mid), valR, valL);
upd(2*i+1, mid+1, r, max(x,mid+1), y, valR, valL);
valsR[i] = max(valsR[2*i], valsR[2*i+1]);
valsL[i] = min(valsL[2*i], valsL[2*i+1]);
}
pair<int,int> query(int i, int l, int r, int x, int y) {
if (y < x) return make_pair(-1,1e9);
if (x == l && y == r) return make_pair(valsR[i],valsL[i]);
int mid = (l+r)/2;
auto q1 = query(2*i,l,mid, x, min(y,mid));
auto q2 = query(2*i+1,mid+1,r, max(x,mid+1), y);
int retR = max(q1.first, max(q2.first, lzR[i]));
int retL = min(q1.second, min(q2.second, lzL[i]));
return make_pair(retR, retL);
}
pair<int,int> query(int x, int y) {return query(1,0,sz-1,x,y);}
void upd(int x, int y, int valR, int valL) {upd(1,0,sz-1,x,y,valR,valL);}
int N,M,Q;
vector<vector<int>> adj(MAX);
vector<pair<int,int>> el;
vector<bool> active(MAX);
set<pair<int,int>> regions;
int main() {
cin >> N >> M >> Q;
for (int i = 0; i < N-1; i++) {
int X,Y;
cin >> X >> Y;
X--; Y--;
adj[X].push_back(Y);
adj[Y].push_back(X);
el.emplace_back(X,Y);
}
for (int i = 0; i < N; i++) {
regions.insert(make_pair(i,i));
upd(i,i,i,i);
// r[i] = i;
// l[i] = i;
}
for (int i = 0; i < M; i++) {
int d;
cin >> d;
d--;
active[d] = !active[d];
int u,v;
tie(u,v) = el[d];
//if (u > v) swap(u,v);
if (active[d]) {
// cout << "adding " << u << " " << v << "\n";
auto cur1 = --regions.lower_bound(make_pair(u+1,-1));
auto cur2 = --regions.lower_bound(make_pair(u+2,-1));
int a = (*cur1).first;
int b = (*cur2).second;
// cout << a << " " << b << "\n";
regions.erase(cur1);
regions.erase(cur2);
regions.insert(make_pair(a,b));
upd(a,b,query(b,b).first,query(a,a).second);
}
if (!active[d]) {
// cout << "removing " << u << " " << v << "\n";
auto cur = --regions.lower_bound(make_pair(u+1,-1));
int a,b;
tie(a,b) = *cur;
regions.erase(cur);
regions.insert(make_pair(a,u));
regions.insert(make_pair(u+1,b));
// cout << a << " " << b << "\n";
}
//edge = el[d];
}
for (int q = 0; q < Q; q++) {
int C;
cin >> C;
C--;
//cout << C << "\n";
cout << query(C,C).first - query(C,C).second + 1 << "\n";
//unique nodes for C
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2688 KB |
Output is correct |
| 2 |
Runtime error |
8 ms |
5248 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
102 ms |
14828 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 |
2688 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2688 KB |
Output is correct |
| 3 |
Runtime error |
9 ms |
5248 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
113 ms |
14596 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 |
11 ms |
5248 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
