Submission #1268527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268527		newbie_t	구슬과 끈 (APIO14_beads)	C++20	100 / 100	53 ms	26140 KiB

beads

#include<cstdio>
#include<climits>
typedef long long ll;
int cnt=0;
ll mx1[200005],mx2[200005],vg[200005];
ll f[200005][2],g[200005][2],k[200005][2];
int son1[200005],son2[200005];
int h[200005],to[400005],ver[400005],w[400005];
inline int read() {
	register int x=0,f=1;register char s=getchar();
	while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
	while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
	return x*f;
}
inline void add(int x,int y,int z) {
	to[++cnt]=y;
	ver[cnt]=h[x];
	w[cnt]=z;
	h[x]=cnt;
}
inline void swap(int &x,int &y) {int tmp=x;x=y;y=tmp;}
inline void swap(ll &x,ll &y) {ll tmp=x;x=y;y=tmp;}
inline ll max(const ll &x,const ll &y) {return x>y? x:y;}
inline void dfs1(int x,int fa) {
	mx1[x]=mx2[x]=INT_MIN; son1[x]=son2[x]=0;
	for(register int i=h[x];i;i=ver[i]) {
		int y=to[i];
		if(y==fa) continue;
		vg[y]=w[i];dfs1(y,x);
		f[x][0]+=max(f[y][0],f[y][1]+w[i]);
		ll val=f[y][0]+w[i]-max(f[y][0],f[y][1]+w[i]);
		if(mx1[x]<val) {son2[x]=son1[x];mx2[x]=mx1[x];son1[x]=y;mx1[x]=val;}
		else if(mx2[x]<val) {son2[x]=y;mx2[x]=val;}	
	}
	f[x][1]=f[x][0]+mx1[x];
}
inline void dfs2(int x,int fa) {
	for(register int i=h[x];i;i=ver[i]) {
		int y=to[i];
		if(y==fa) continue;
		if(son1[x]==y) {swap(mx1[x],mx2[x]);swap(son1[x],son2[x]);}
		k[x][0]=g[x][0]-max(f[y][0],f[y][1]+w[i]);k[x][1]=k[x][0]+mx1[x];
		if(fa!=-1) {k[x][1]=max(k[x][1],k[x][0]+k[fa][0]+vg[x]-max(k[fa][0],k[fa][1]+vg[x]));}
		g[y][0]=f[y][0]+max(k[x][0],k[x][1]+w[i]);
		if(mx1[x]<mx2[x]) {swap(mx1[x],mx2[x]);swap(son1[x],son2[x]);}
		dfs2(y,x);
	}
}
int main() {
	int n=read(); ll ans=0;
	for(register int i=1;i<n;++i) {int x=read(),y=read(),z=read(); add(x,y,z);add(y,x,z);}
	dfs1(1,-1); g[1][0]=f[1][0]; dfs2(1,-1);
	for(register int i=1;i<=n;++i) ans=max(ans,g[i][0]);
	printf("%lld",ans);
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int read()':
beads.cpp:10:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   10 |         register int x=0,f=1;register char s=getchar();
      |                      ^
beads.cpp:10:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   10 |         register int x=0,f=1;register char s=getchar();
      |                          ^
beads.cpp:10:44: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   10 |         register int x=0,f=1;register char s=getchar();
      |                                            ^
beads.cpp: In function 'void dfs1(int, int)':
beads.cpp:26:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   26 |         for(register int i=h[x];i;i=ver[i]) {
      |                          ^
beads.cpp: In function 'void dfs2(int, int)':
beads.cpp:38:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   38 |         for(register int i=h[x];i;i=ver[i]) {
      |                          ^
beads.cpp: In function 'int main()':
beads.cpp:51:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   51 |         for(register int i=1;i<n;++i) {int x=read(),y=read(),z=read(); add(x,y,z);add(y,x,z);}
      |                          ^
beads.cpp:53:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   53 |         for(register int i=1;i<=n;++i) ans=max(ans,g[i][0]);
      |                          ^

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43