Submission #1626759

---

Source Code Expand

#include<bits/stdc++.h>
const int N=133333;
typedef long long i64;
#define LC lc[ns]
#define RC rc[ns]
int n;
i64 L=0,R=0,M;
struct pos{
	i64 x,y;
}mem[N*40],*mp=mem;
struct node{
	int lc,rc,sz,ap;
	i64 dep;
	pos*as;
	void ac(int x){(lc?rc:lc)=x;}
	void alloc(int n){as=mp,mp+=n;}
	void push(const pos&w){
		if(ap&&as[ap-1].y<=w.y)return;
		as[ap++]=w;
	}
	void mg(node&a,node&b){
		pos*ls=a.as,*rs=b.as;
		int lp=a.ap,rp=b.ap,pp=0;
		i64 lim=M+dep*2;
		ap=0;
		int i,j;
		for(i=0,j=0;i<rp;++i){
			for(;j<lp&&ls[j].x+rs[i].y<=lim;++j);
			if(j)mp[pp++]=(pos){rs[i].x,ls[j-1].y};
		}
		j=0;
		for(i=pp-1;i>=0;--i){
			for(;j<pp&&mp[j].x<mp[i].y;push(mp[j++]));
			push((pos){mp[i].y,mp[i].x});
		}
		for(;j<pp;push(mp[j++]));
	}
}ns[N];
void f1(int x){
	node&w=ns[x];
	if(w.lc){
		w.LC.dep+=w.dep;
		w.RC.dep+=w.dep;
		f1(w.lc);
		f1(w.rc);
		w.sz=w.LC.sz+w.RC.sz;
		if(w.LC.sz<w.RC.sz)std::swap(w.lc,w.rc);
		w.alloc(w.RC.sz*2);
	}else{
		w.sz=1;
		w.alloc(1);
	}
}
void f2(int x){
	node&w=ns[x];
	if(w.lc){
		f2(w.lc);
		f2(w.rc);
		w.mg(w.LC,w.RC);
	}else{
		w.ap=0;
		w.push((pos){w.dep,w.dep});
	}
}
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n;++i){
		int f,d;
		scanf("%d%d",&f,&d);
		ns[i].dep=d;
		ns[f].ac(i);
		R+=d;
	}
	f1(1);
	while(L<R){
		M=L+R>>1;
		f2(1);
		if(ns[1].ap)R=M;
		else L=M+1;
	}
	printf("%lld\n",L);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:69:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&f,&d);
                      ^

Judge Result