QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#478 | #249482 | #7626. Quake and Rebuild | ship2077 | grass8cow | Failed. | 2023-12-04 09:27:42 | 2023-12-04 09:33:53 |
Details
Extra Test:
Accepted
time: 194ms
memory: 9036kb
input:
200000 200000 1 1 2 4 5 3 2 7 6 10 4 3 13 7 7 3 13 13 8 5 16 15 17 5 10 14 18 24 22 13 3 7 32 6 27 36 31 16 22 38 14 35 36 4 23 9 1 26 43 25 31 9 48 31 15 1 49 2 55 59 16 16 3 53 5 19 15 14 14 10 51 40 48 58 28 55 49 19 72 53 43 64 10 43 64 8 38 5 44 66 62 69 63 84 95 64 53 36 23 3 60 25 51 55 45 85...
output:
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
result:
ok 100000 lines
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#249482 | #7626. Quake and Rebuild | grass8cow | AC ✓ | 1902ms | 9980kb | C++14 | 2.5kb | 2023-11-12 09:35:21 | 2024-11-20 20:28:49 |
answer
#include<bits/stdc++.h>
using namespace std;
int n,q,f[200100],tag[1010],ok[1010],L[1010],R[1010];
int fa[200100];
const int P=510;
int ip[201000];
int dfn[200010],d[201000];
void build(int t){
if(ok[t])return;
for(int i=L[t];i<=R[t];i++){
fa[i]=i;
int e=f[i]-tag[t];
if(e>=L[t])fa[i]=fa[e],d[i]=d[e]+1;
else d[i]=0;
}
ok[t]=1;
for(int i=L[t];i<=R[t];i++)ok[t]&=(fa[i]==i);
}
int ff(int u){return max(1,f[fa[u]]-tag[ip[u]]);}
int nf(int u){return max(1,f[u]-tag[ip[u]]);}
int lca(int u,int v){
while(1){
if(ip[u]<ip[v])swap(u,v);
if(ip[u]>ip[v]||fa[u]!=fa[v])u=ff(u);
else break;
}
while(u!=v){if(u<v)swap(u,v);u=nf(u);}
return u;
}
int dep(int u){
int s=0;while(u!=1)s+=d[u]+1,u=ff(u);
return s;
}
bool gm[201000],gt[201000];
int be[201000],mm[510][510],ts[510],ans;
void sol(int x){
bool fl=0;
for(int i=1;i<=ts[x];i++)fl|=gt[fa[mm[x][i]]],gt[fa[mm[x][i]]]=1;
if(fl){
for(int i=R[x];i>=L[x];i--){
gt[i]=0;
if(gm[i]){
ans++;int e=nf(i);
if(e>=L[x])gm[e]=1;
else{if(!gm[e])gm[e]=1,mm[ip[e]][++ts[ip[e]]]=e;}
}
}
for(int i=L[x];i<=R[x];i++)gm[i]=0;
}
else{
for(int i=1;i<=ts[x];i++){
gm[mm[x][i]]=0;
ans+=d[mm[x][i]]+1,gt[fa[mm[x][i]]]=0;
int e=ff(mm[x][i]);
if(!gm[e])gm[e]=1,mm[ip[e]][++ts[ip[e]]]=e;
}
}
}
int main(){
cin>>n>>q;
for(int i=2;i<=n;i++)scanf("%d",&f[i]),ip[i]=1+(i-2)/P;
fa[1]=1;
int now=2,p=0;
while(now<=n){L[++p]=now;R[p]=min(n,now+P-1);now+=P;}
for(int i=1;i<=p;i++)build(i);
while(q--){
int type,l,r,x;
scanf("%d",&type);
if(type==1){
scanf("%d%d%d",&l,&r,&x);
int il=ip[l],ir=ip[r];
if(il==ir){
int t=il;
for(int i=l;i<=r;i++)f[i]=max(f[i]-x,1);
build(t);
}
else{
for(int i=l;i<=R[il];i++)f[i]=max(f[i]-x,1);
build(il);
for(int i=L[ir];i<=r;i++)f[i]=max(f[i]-x,1);
build(ir);
for(int i=il+1;i<ir;i++)tag[i]=min(tag[i]+x,n),build(i);
}
}
else{
scanf("%d",&x);
for(int i=1;i<=x;i++)scanf("%d",&be[i]);
int lc=be[1];for(int i=2;i<=x;i++)lc=lca(lc,be[i]);
if(x>P){
for(int i=1;i<=x;i++)gm[be[i]]=1;
ans=1;
for(int i=n;i>=2;i--)if(gm[i])ans++,gm[nf(i)]=1;
memset(gm,0,sizeof(gm));
printf("%d\n",ans-dep(lc));continue;
}
else{
ans=1;
memset(ts,0,sizeof(ts));
for(int i=1;i<=x;i++)if(!gm[be[i]])
gm[be[i]]=1,ts[ip[be[i]]]++,mm[ip[be[i]]][ts[ip[be[i]]]]=be[i];
for(int i=ip[n];i;i--)sol(i);
printf("%d\n",ans-dep(lc));continue;
}
}
}
return 0;
}