QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225670#7433. 梦想歌zhouhuanyiWA 5ms32972kbC++232.4kb2023-10-24 22:39:382023-10-24 22:39:38

Judging History

你现在查看的是最新测评结果

  • [2023-10-24 22:39:38]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:32972kb
  • [2023-10-24 22:39:38]
  • 提交

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'