QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61989 | #4387. Static Query on Tree | luyiming123 | TL | 0ms | 0kb | C++14 | 3.9kb | 2022-11-16 15:50:10 | 2022-11-16 15:50:12 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 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;
struct node
{
int 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; int tag = T[root].tag[opt],mid = (l + r) >> 1;
T[root << 1].val[opt] += tag * (mid - l + 1),T[root << 1 | 1].val[opt] += tag * (r - mid);
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,int d,int opt)
{
if(l <= s && t <= r)
{
T[root].val[opt] += d * (t - s + 1),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;
}
int 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;
int ans = 0;
if(x <= mid) ans += query(root << 1,l,mid,x,opt);
else ans += query(root << 1 | 1,mid + 1,r,x,opt);
return ans;
}
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,int 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,int d,int opt)
{
update(1,dfn[x],dfn[x] + siz[x] - 1,1,dfntot,d,opt); return;
}
int main(void)
{
scanf("%d",&Test);
while(Test--)
{
scanf("%d%d",&n,&q);
for(int i = 1; i <= n; i++) g[i].clear();
for(int i = 2; i <= n; i++)
{
int f; scanf("%d",&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--)
{
scanf("%d%d%d",&NA,&NB,&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; scanf("%d",&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; scanf("%d",&x);
Modify_Path(1,x,1,1); //OptA.push_back({x,1});
}
for(int i = 1; i <= NC; i++)
{
int x; scanf("%d",&x);
Modify_Subtree(x,1,2);// OptB.push_back({x,2});
}
int total = 0;
for(int i = 1; i <= n; i++)
{
int x = query(1,1,dfntot,dfn[i],0),y = query(1,1,dfntot,dfn[i],1),z = query(1,1,dfntot,dfn[i],2);
// printf("i = %d,x = %d,y = %d,z = %d\n",i,x,y,z);
if(x && y && z) ++total;
}
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 ...