QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225670 | #7433. 梦想歌 | zhouhuanyi | WA | 5ms | 32972kb | C++23 | 2.4kb | 2023-10-24 22:39:38 | 2023-10-24 22:39:38 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#define N 400000
using namespace std;
long long read()
{
char c=0;
long long sum=0,f=1;
while (c!='-'&&(c<'0'||c>'9')) c=getchar();
if (c=='-') c=getchar(),f=-1;
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum*f;
}
int n,q,szt,leng,length,depth[N+1],rt[N+1],ls[N+1],rs[N+1],lg[N+1],dfn[N+1],rev[N+1],sz[N+1],block[N+1],fa[N+1][21];
long long a[N+1];
__int128 lazy[N+1],lazy2[N+1];
vector<int>E[N+1];
void merge(int x,int y)
{
++length,ls[length]=rt[x],rs[length]=rt[y],fa[ls[length]][0]=fa[rs[length]][0]=length,rt[y]=length;
return;
}
void dfs(int x)
{
rt[x]=x;
for (int i=0;i<E[x].size();++i) dfs(E[x][i]),merge(E[x][i],x);
return;
}
void dfs2(int x)
{
dfn[x]=++leng,rev[dfn[x]]=x;
if (ls[x]) depth[ls[x]]=depth[rs[x]]=depth[x]+1,dfs2(ls[x]),dfs2(rs[x]),sz[x]=sz[ls[x]]+sz[rs[x]]+1;
else sz[x]=1;
return;
}
void add(int x,long long d)
{
for (int i=block[x]+1;i<=leng;++i) lazy[i]+=d;
for (int i=x;i<=min(block[x]*szt,leng);++i) lazy2[i]+=d;
return;
}
long long query(int x)
{
return lazy[block[x]]+lazy2[x];
}
long long get_sz(int x)
{
return query(dfn[x]+sz[x]-1)-query(dfn[x]-1);
}
int get_centroid(int x)
{
int ps=dfn[x]-1,y;
long long d=query(dfn[x]-1),d2=query(dfn[x]+sz[x]-1)-d;
for (int i=lg[sz[x]];i>=0;--i)
if (ps+(1<<i)<=dfn[x]+sz[x]-1&&((query(ps+(1<<i))-d)<<1)<d2)
ps+=(1<<i);
ps++,y=rev[ps];
if ((get_sz(y)<<1)>d2) return y;
for (int i=lg[depth[y]-depth[x]];i>=0;--i)
if (depth[fa[y][i]]>=depth[x]&&(get_sz(fa[y][i])<<1)<=d2)
y=fa[y][i];
return fa[y][0];
}
int main()
{
int op,x,y;
long long d;
for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
length=n=read(),q=read();
for (int i=1;i<=n;++i) a[i]=read();
for (int i=2;i<=n;++i) x=read(),E[x].push_back(i);
dfs(1),depth[length]=1,dfs2(length),szt=sqrt(length);
for (int i=1;i<=lg[length];++i)
for (int j=1;j<=length;++j)
fa[j][i]=fa[fa[j][i-1]][i-1];
for (int i=1;i<=length;++i) block[i]=(i-1)/szt+1;
for (int i=1;i<=n;++i) add(dfn[i],a[i]);
for (int i=1;i<=q;++i)
{
op=read();
if (op==1)
{
x=read(),x=rt[x];
while (ls[x])
{
y=get_centroid(x);
if (ls[y])
{
if (get_sz(sz[ls[y]])>get_sz(sz[rs[y]])) x=ls[y];
else x=rs[y];
}
else x=y;
}
printf("%lld\n",a[x]);
}
else x=read(),d=read(),a[x]+=d,add(dfn[x],d);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 5ms
memory: 32972kb
input:
1000 1000 789235149 971630276 32611109 914526454 322116555 603760422 515825265 152313854 448798679 318603927 286945416 136257807 504937778 335098720 99992633 383505822 680671658 103868338 645514353 842590958 30634297 935721702 280349478 690724214 918666175 189139505 674200041 396011000 363889197 296...
output:
600944721 586991223 725908539 243994087 251109043 991048632 788383814 260115709 923674726 9265023 962138031 612845865 448729347 285660823 866037625 401577003 905476949 957366550 484438754 127214516 195856238 373322009 22657345 256924256 735141176 823287132 356178355 542108952 490075331 381577999 377...
result:
wrong answer 2nd numbers differ - expected: '649102944', found: '586991223'