QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61996 | #4387. Static Query on Tree | luyiming123 | TL | 0ms | 0kb | C++14 | 4.5kb | 2022-11-16 16:30:05 | 2022-11-16 16:30:08 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int Test,n,q;
int NA,NB,NC;
vector <int> g[N];
int siz[N],top[N],dfn[N],son[N],dep[N],f[N],dfntot = 0;
template <typename T> void read(T &x)
{
int w = 1; x = 0; char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-') w = -1;
ch = getchar();
}
while(isdigit(ch))
{
x = x * 10 + ch - '0'; ch = getchar();
}
x *= w; return;
}
struct node
{
bool val[3],tag[3];
}T[N << 2];
void pushup(int root)
{
for(int i = 0; i <= 2; i++)
T[root].val[i] = T[root << 1].val[i] & T[root << 1 | 1].val[i];
return;
}
void build(int root,int l,int r,int opt)
{
T[root].val[opt] = T[root].tag[opt] = 0;
if(l == r)
{
return;
}
int mid = (l + r) >> 1;
build(root << 1, l,mid,opt),build(root << 1 | 1, mid + 1,r,opt);
return;
}
void pushdown(int root,int l,int r,int opt)
{
if(T[root].tag[opt] == 0) return; bool tag = T[root].tag[opt];
T[root << 1].val[opt] |= tag,T[root << 1 | 1].val[opt] |= tag;
T[root << 1].tag[opt] |= tag,T[root << 1 | 1].tag[opt] |= tag;
T[root].tag[opt] = 0;
return;
}
void update(int root,int l,int r,int s,int t,bool d,int opt)
{
// printf("UPD : l = %d,r = %d,s = %d,t = %d,opt = %d\n",l,r,s,t,opt);
if(l <= s && t <= r)
{
T[root].val[opt] |= d,T[root].tag[opt] |= d;
return;
}
pushdown(root,s,t,opt);
int mid = (s + t) >> 1;
if(l <= mid) update(root << 1,l,r,s,mid,d,opt);
if(r > mid) update(root << 1 | 1,l,r,mid + 1,t,d,opt);
pushup(root); return;
}
bool query(int root,int l,int r,int x,int opt)
{
if(l == r) return T[root].val[opt];
pushdown(root,l,r,opt);
int mid = (l + r) >> 1;
if(x <= mid) return query(root << 1,l,mid,x,opt);
else return query(root << 1 | 1,mid + 1,r,x,opt);
}
void Pr(int root,int l,int r)
{
// printf("root = %d,l = %d,r = %d,val0 = %d,va1l = %d,val2 = %d\n",root,l,r,T[root].val[0],T[root].val[1],T[root].val[2]);
if(l == r) return; int mid = (l + r) >> 1;
Pr(root << 1,l,mid),Pr(root << 1 | 1,mid + 1,r); return ;
}
void dfs1(int x,int fa)
{
siz[x] = 1,f[x] = fa,dep[x] = dep[fa] + 1;
for(int i = 0; i < (int)g[x].size(); i++)
{
int v = g[x][i];
if(v == fa) continue;
dfs1(v,x);
siz[x] += siz[v];
if(son[x] == 0 || siz[v] > siz[son[x]]) son[x] = v;
}
return;
}
void dfs2(int x,int t)
{
top[x] = t;
dfn[x] = ++dfntot;
if(son[x]) dfs2(son[x],t);
for(int i = 0; i < (int)g[x].size(); i++)
{
int v = g[x][i];
if(v == f[x] || v == son[x]) continue;
dfs2(v,v);
}
return;
}
void Modify_Path(int x,int y,bool d,int opt)
{
while(top[x] != top[y])
{
if(dep[top[x]] > dep[top[y]]) swap(x,y);
update(1,dfn[top[y]],dfn[y],1,dfntot,d,opt),y = f[top[y]];
}
if(dfn[x] > dfn[y]) swap(x,y);
update(1,dfn[x],dfn[y],1,dfntot,d,opt);
return;
}
void Modify_Subtree(int x,bool d,int opt)
{
update(1,dfn[x],dfn[x] + siz[x] - 1,1,dfntot,d,opt); return;
}
int Find(int root,int l,int r)
{
for(int i = 0; i < 3; i++)pushdown(root,l,r,i);
bool flag = 1;
for(int i = 0; i < 3; i++)
if(!T[root].val[i]) {flag = 0; break;
}
if(flag == 1) return r - l + 1;
else if(l == r) return 0;
int mid = (l + r) >> 1;
int ans = Find(root << 1,l,mid) + Find(root << 1 | 1,mid + 1,r);
return ans;
}
int main(void)
{
read(Test);
while(Test--)
{
read(n),read(q);
for(int i = 1; i <= n; i++) g[i].clear();
for(int i = 2; i <= n; i++)
{
int f; read(f);
g[f].push_back(i),g[i].push_back(f);
}
dfs1(1,0),dfs2(1,1);
// for(int i = 1; i <= n; i++)
// fprintf(stderr,"dep[%d] = %d,dfn[%d] = %d,siz[%d] = %d,top[%d] = %d,son[%d] = %d\n",i,dep[i],i,dfn[i],i,siz[i],i,top[i],i,son[i]);
while(q--)
{
read(NA),read(NB),read(NC);
for(int i = 0; i < 3; i++) build(1,1,dfntot,i);
// vector <pair<int,int> > OptA,OptB;
for(int i = 1; i <= NA; i++)
{
int x; read(x);
// fprintf(stderr,"MP: i = %d\n",i);
Modify_Path(1,x,1,0); //OptA.push_back({x,0});
// fprintf(stderr,"Final.\n");
}
for(int i = 1; i <= NB; i++)
{
int x; read(x);
Modify_Path(1,x,1,1); //OptA.push_back({x,1});
}
for(int i = 1; i <= NC; i++)
{
int x; read(x);
Modify_Subtree(x,1,2);// OptB.push_back({x,2});
}
// Pr(1,1,n);
int total = Find(1,1,n);
printf("%d\n",total);
// for(int i = 0; i < (int)OptA.size(); i++) Modify_Path(1,OptA[i].first,-1,OptA[i].second);
// for(int i = 0; i < (int)OptB.size(); i++) Modify_Subtree(OptB[i].first,-1,OptB[i].second);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
1 200000 18309 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...