#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
//#define int long long
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 1e5+20;
const int MAXA = 2e5+10;
const int LOG = 19;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
int n, m, q;
int u[MAXN], v[MAXN];
vector <int> adj[MAXN];
int par[MAXN], sub[MAXN], dep[MAXN], idx[MAXN];
int root[MAXN];
vector <int> ch[MAXN]; //isi chain
int ty[MAXA];
struct node {
int bit[2*MAXN];
// que
int que(int x){ // mulai dari idx dep[x], cari ke atas yg duluan 1
int dp = dep[x];
int te = 0; // value suffix
for(int i=dp; i>=1; i-=i&(-i)) te += bit[i];
//cout << te << ' ' << x << " te\n";
if(te==0) return -1; // gk ketemu
//cout << " pp\n";
// skrg cari te-1
int ret = 0, sum = 0;
for(int i=LOG-1; i>=0; i--){
if(ret + (1<<i) <= 2*MAXN-10 && sum+bit[ret+(1<<i)] <= te-1){
sum += bit[ret+(1<<i)];
ret += (1<<i);
}
}
// ret+1 --> depth dr yg valnya 1
int ids = ret+1 - dep[root[x]]; // ids dari ch
//cout << ids << " ids\n";
return ch[root[x]][ids]; // idx yg valuenya 1
}
// upd
void upd(int x, int y){ // depth dr idx = x
for(int i=x; i<=2*MAXN-10; i+=i&(-i)) bit[i] += y;
}
} *st[MAXN];
int query(int x){ // x --> idx nya
while(st[x]->que(x) == -1){
if(x==0) assert(false);
x = par[root[x]];
}
// udh ketemu
return st[x]->que(x); // idxnya
}
void update(int x, int nw){ // idx x += nw
st[x]->upd(dep[x], nw);
}
void dfs(int nw, int pa){
par[nw] = pa; sub[nw] = 1; dep[nw] = dep[pa]+1;
for(auto nx : adj[nw]){
if(nx == pa) continue;
dfs(nx, nw);
sub[nw] += sub[nx];
}
}
void build(int x, int y){
st[x] = new node();
for(int i=dep[x]+1; i<=dep[y]; i++) st[idx[i]] = st[x];
}
int val[MAXN], up[MAXN];
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m >> q;
for(int i=1; i<=n-1; i++){
cin >> u[i] >> v[i];
adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]);
}
dfs(1, 0);
for(int i=1; i<=n-1; i++){
if(dep[u[i]] > dep[v[i]]) swap(u[i], v[i]);
}
queue<int> qu; qu.push(1);
while(!qu.empty()){
int nw = qu.front(); int tp = nw; qu.pop();
while(true){
ch[tp].pb(nw);
root[nw] = tp;
idx[dep[nw]] = nw;
int big = n+1;
for(auto nx : adj[nw]){
if(nx==par[nw]) continue;
if(sub[nx] > sub[big]) big = nx;
}
if(big==n+1) break;
for(auto nx : adj[nw]){
if(nx==par[nw] || nx==big) continue;
qu.push(nx);
}
nw = big;
}
build(tp, nw);
if(qu.size() > n) assert(false);
}
int ins = 0;
for(int i=1; i<=n; i++) ins += ch[i].size();
if(ins > n) assert(false);
for(int i=1; i<=n; i++){
update(i, 1);
val[i] = 1; up[i] = 0;
}
for(int i=1; i<=m; i++){
int x; cin >> x;
//cout << u[x] << ' ' << v[x] << " atas\n";
ty[x] = 1-ty[x];
if(ty[x]){ // ke nyala, join
update(v[x], -1); //yg bawah
int idx = query(u[x]);
val[idx] = val[idx]+val[v[x]]-up[v[x]];
} else { // ke mati
int idx = query(v[x]);
//cout << i << ' ' << x << ' ' << idx << " idx\n";
update(v[x], 1);
val[v[x]] = val[idx];
up[v[x]] = val[idx];
}
// for(int j=1; j<=n; j++){
// cout << j << ' '<< val[j] << ' ' << up[j] << " up\n";
// }
}
while(q--){
int x; cin >> x;
int anc = query(x);
cout << val[anc] << '\n';
//cout << anc << ' ' << " anc\n";
}
}
Compilation message
synchronization.cpp: In function 'int main()':
synchronization.cpp:120:22: warning: comparison of integer expressions of different signedness: 'std::queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
120 | if(qu.size() > n) assert(false);
| ~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13148 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10076 KB |
Output is correct |
| 4 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 5 |
Correct |
16 ms |
50012 KB |
Output is correct |
| 6 |
Runtime error |
96 ms |
262144 KB |
Execution killed with signal 9 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
112 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10076 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10076 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10076 KB |
Output is correct |
| 4 |
Correct |
3 ms |
10072 KB |
Output is correct |
| 5 |
Correct |
2 ms |
10096 KB |
Output is correct |
| 6 |
Correct |
2 ms |
10076 KB |
Output is correct |
| 7 |
Correct |
10 ms |
10844 KB |
Output is correct |
| 8 |
Correct |
87 ms |
18124 KB |
Output is correct |
| 9 |
Correct |
88 ms |
18036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
18120 KB |
Output is correct |
| 2 |
Correct |
65 ms |
18380 KB |
Output is correct |
| 3 |
Correct |
61 ms |
18480 KB |
Output is correct |
| 4 |
Correct |
62 ms |
18564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13148 KB |
Output is correct |
| 3 |
Correct |
4 ms |
13916 KB |
Output is correct |
| 4 |
Correct |
15 ms |
45404 KB |
Output is correct |
| 5 |
Runtime error |
106 ms |
262144 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
