// in the name of ALLAH
#include<bits/stdc++.h>
using namespace std;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(l, r) ((l+r)>>1)
#define lb(x) (x&(-x))
#define pii pair<int, int>
#define F first
#define S second
const int N = 1e5+5, M = 2e5+5;
int SZ[N], FRST[N], LST[N], RT[N], DF[M], n, m, q, sz;
vector<pii> adj[N], Yals[N];
vector<int> verts;
bitset<N> B;
struct DS{
struct node { int mn, mx, lz; } D[M<<3];
struct undo { int id; node nd; } STK[M*300];
int stk=0;
inline void ad(int id) { STK[stk++]={id, D[id]}; }
inline void merg(int id) { D[id].mx=max(D[L(id)].mx, D[R(id)].mx); D[id].mn=min(D[L(id)].mn, D[R(id)].mn); }
void build(int id = 1, int l = 0, int r = m+3){
if(r-l<2) { D[id]={l, l, -1}; return; }
int mid = MID(l, r);
build(L(id), l, mid);
build(R(id), mid, r);
merg(id);
D[id].lz=-1;
}
inline void shift(int id){
int d=D[id].lz;
if(!(~d)) return;
ad(L(id)); ad(R(id));
D[L(id)] = D[R(id)] = {d, d, d};
}
void addlst(int s, int e, int id = 1, int l = 0, int r = m+3){
if(D[id].mn>e||D[id].mx<s) return;
if(D[id].mn>=s&&D[id].mx<=e) { ad(id); D[id] = {e, e, e}; return; }
int mid = MID(l, r);
shift(id);
addlst(s, e, L(id), l, mid);
addlst(s, e, R(id), mid, r);
ad(id); merg(id);
}
void addfrst(int s, int e, int d, int id = 1, int l = 0, int r = m+3){
if(l>=e || r<=s) return;
if(l>=s && r<=e) { ad(id); D[id]={d, d, d}; return; }
if(r-l<2) return;
int mid = MID(l, r);
shift(id);
addfrst(s, e, d, L(id), l, mid);
addfrst(s, e, d, R(id), mid, r);
ad(id); merg(id);
}
int getLST(int id = 1, int l = 0, int r = m+3){
if(r-l<2) { if(D[id].mn>=m+2) return(-1); return(l); }
int mid = MID(l, r);
shift(id);
if(D[R(id)].mn<m+2) return(getLST(R(id), mid, r));
return(getLST(L(id), l, mid));
}
int getind(int ind, int id = 1, int l = 0, int r = m+3){
if(r-l<2) return(D[id].mn);
int mid = MID(l, r);
shift(id);
if(ind<mid) return(getind(ind, L(id), l, mid));
return(getind(ind, R(id), mid, r));
}
inline void redo(int x) { while(stk>x) { stk--; D[STK[stk].id]=STK[stk].nd; } }
} frst, lst;
inline void add(int ind, int d) { for(ind++;ind<M;ind+=lb(ind)) DF[ind]+=d; }
inline int get(int ind){
int sm=0; for(ind++;ind;ind-=lb(ind)) sm+=DF[ind];
return(sm);
}
void setsz(int u, int p) { SZ[u]=1; for(pii&x:adj[u]) if(x.F^p&&!B[x.F]) { setsz(x.F, u); SZ[u]+=SZ[x.F]; } }
int getrt(int u, int p) { for(pii&x:adj[u]) if(x.F^p&&!B[x.F]&&SZ[x.F]>=(sz>>1)) return(getrt(x.F, u)); return(u); }
void ini(int u, int p) { verts.push_back(u); for(pii&x:adj[u]) if(x.F^p&&!B[x.F]) ini(x.F, u); }
void DFSlst(int u, int p){
if(!(~LST[p])) return;
int f1=lst.stk;
LST[u]=lst.getLST();
if(!(~LST[u])) { lst.redo(f1); return; }
for(pii&x:adj[u]) if(x.F^p&&!B[x.F]){
int f2=lst.stk;
vector<pii>&v=Yals[x.S];
if(v.empty()) { lst.addlst(0, m+2); DFSlst(x.F, u); lst.redo(f2); continue; }
lst.addlst(0, v[0].F);
for(int i=0;i<(int)v.size()-1;i++) lst.addlst(v[i].S+1, v[i+1].F);
lst.addlst(v.back().S+1, m+2);
DFSlst(x.F, u);
lst.redo(f2);
}
lst.redo(f1);
}
void DFSfrst(int u, int p){
if(FRST[p]>=m+2) return;
int f1=frst.stk;
FRST[u]=frst.getind(0);
if(FRST[u]>=m+2) { frst.redo(f1); return; }
for(pii&x:adj[u]) if(x.F^p&&!B[x.F]){
int f2=frst.stk;
vector<pii>&v=Yals[x.S];
if(v.empty()) { frst.addfrst(0, m+3, m+2); DFSfrst(x.F, u); frst.redo(f2); continue; }
frst.addfrst(v.back().S+1, m+3, m+2);
for(int i=(int)v.size()-2;~i;i--){
int gt=frst.getind(v[i+1].F);
frst.addfrst(v[i].S+1, v[i+1].F, gt);
}
int gt=frst.getind(v[0].F);
frst.addfrst(0, v[0].F, gt);
DFSfrst(x.F, u);
frst.redo(f2);
}
frst.redo(f1);
}
void emal(int u, int p, int d){
if(FRST[u]<m+2){
add(FRST[u], d);
for(pii&x:adj[u]) if(x.F^p&&!B[x.F]) emal(x.F, u, d);
}
}
void Do(int u, int p){
if(~LST[u]){
RT[u]+=get(LST[u]);
for(pii&x:adj[u]) if(x.F^p&&!B[x.F]) Do(x.F, u);
}
}
inline void darkol(int u){
setsz(u, 0); sz=SZ[u]; u=getrt(u, 0);
B[u]=1; for(pii&x:adj[u]) if(!B[x.F]) darkol(x.F); B[u]=0;
while(verts.size()) verts.pop_back();
ini(u, 0);
for(int&x:verts) { FRST[x]=m+2; LST[x]=-1; }
DFSlst(u, 0);
DFSfrst(u, 0);
for(int t=0;t<2;t++){
for(pii&x:adj[u]) if(!B[x.F]){
Do(x.F, u);
emal(x.F, u, 1);
}
for(pii&x:adj[u]) if(!B[x.F]) emal(x.F, u, -1);
reverse(adj[u].begin(), adj[u].end());
}
for(int&x:verts) if(x^u){
if(FRST[x]<m+2) RT[u]++;
if(~LST[x]) RT[x]++;
}
}
int main(){
scanf("%d %d %d", &n, &m, &q);
frst.build(); lst.build();
for(int i=1;i<n;i++){
int a, b; scanf("%d %d", &a, &b);
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
memset(LST, -1, sizeof(LST));
for(int i=1;i<=m;i++){
int a; scanf("%d", &a);
if(~LST[a]) { Yals[a].push_back({LST[a], i}); LST[a]=-1; }
else LST[a]=i;
}
for(int i=1;i<n;i++) if(~LST[i]) Yals[i].push_back({LST[i], m+1});
LST[0]=0;
darkol(1);
for(int Q=0;Q<q;Q++){
int a; scanf("%d", &a);
printf("%d\n", RT[a]+1);
}
}
Compilation message
synchronization.cpp: In function 'int main()':
synchronization.cpp:151:10: 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:154:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:160:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a; scanf("%d", &a);
~~~~~^~~~~~~~~~
synchronization.cpp:168:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a; scanf("%d", &a);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5504 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 4 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 6 |
Correct |
13 ms |
5760 KB |
Output is correct |
| 7 |
Correct |
156 ms |
7972 KB |
Output is correct |
| 8 |
Correct |
111 ms |
8028 KB |
Output is correct |
| 9 |
Correct |
155 ms |
8060 KB |
Output is correct |
| 10 |
Correct |
1827 ms |
27168 KB |
Output is correct |
| 11 |
Incorrect |
1930 ms |
27124 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2083 ms |
113456 KB |
Output is correct |
| 2 |
Correct |
2125 ms |
117100 KB |
Output is correct |
| 3 |
Correct |
3131 ms |
122056 KB |
Output is correct |
| 4 |
Correct |
3103 ms |
123476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5504 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5448 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
5476 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1133 ms |
32968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5504 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5504 KB |
Output is correct |
| 4 |
Incorrect |
10 ms |
5632 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
