Submission #19172

#	Time	Username	Problem	Language	Result	Execution time	Memory
19172		comet	Beads and wires (APIO14_beads)	C++14	57 / 100	1074 ms	79716 KiB

beads

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cassert>
#include <unordered_map>
#define pb push_back
using namespace std;
typedef pair<int,int> pp;
struct pt{int u,c;};
typedef vector<int> vec;
typedef vector<pt> vec2;
typedef vector<vec> mat;
typedef vector<vec2> graph;

unordered_map<int,int> ID[200010];

mat dp[2];
graph path;

int N;
int root;
bool chk[200010];
int sum[200010];
int Max[200010][2];
int Maxi[200010][2];
int par[200010];

void input(){
	scanf("%d",&N);
	path.assign(N+1,vec2());
	dp[0].assign(N+1,vec());
	dp[1].assign(N+1,vec());

	int x,y,z;
	for(int i=0;i<N-1;i++){
		scanf("%d%d%d",&x,&y,&z);
		ID[x][y]=path[x].size();
		ID[y][x]=path[y].size();
		path[x].pb(pt{y,z});
		path[y].pb(pt{x,z});
		dp[0][x].pb(-1);dp[1][x].pb(-1);
		dp[0][y].pb(-1);dp[1][y].pb(-1);
	}
	for(int i=1;i<=N;i++){
		ID[i][i]=path[i].size();
		dp[0][i].pb(-1);
		dp[1][i].pb(-1);
	}
}

int getMax(int v,vec2& a){
	int Max1=-1e9,Max2=-1e9;
	int id1=0,id2=0;
	for(int i=0;i<a.size();i++){
		if(a[i].c>=Max1){
			Max2=Max1;
			id2=id1;
			Max1=a[i].c;
			id1=a[i].u;
		}else if(a[i].c>Max2){
			Max2=a[i].c;
			id2=a[i].u;
		}
	}
	Max[v][0]=Max1;Maxi[v][0]=id1;
	Max[v][1]=Max2;Maxi[v][1]=id2;
	return Max1;
}

void process(int v,int p,int mode){
	int sz=path[v].size();
	int cnt=sz-(v!=root);
	int& ret=dp[mode][v][ID[v][p]];
	ret=0;
	if(cnt==0){
		if(mode==1)ret = -1e9;
		return;
	}

	vec2 a;
	sum[v]=0;
	for(int i=0;i<sz;i++){
		int u=path[v][i].u;
		int c=path[v][i].c;
		int id=ID[u][v];
		if(p==u)continue;
		int z = max(dp[0][u][id],dp[1][u][id]+c);
		sum[v]+=z;
		if(mode==1){
			a.pb(pt{u,dp[0][u][id]+c-z});
		}
	}

	ret=sum[v];
	if(mode==1){
		ret+=getMax(v,a);
	}
}

void dfs(int v,int p,int mode){

	int& ret=dp[mode][v][ID[v][p]];
	if(~ret)return;
	
	par[v]=p;
	for(int i=0;i<path[v].size();i++){
		int u=path[v][i].u;
		if(u==p)continue;
		dfs(u,v,0);
		dfs(u,v,1);
	}
	
	process(v,p,mode);
//	printf("%d %d %d : %d\n",v,p,mode,dp[mode][v][ID[v][p]]);
}

void process2(int v,int p,int mode){
	int sz=path[v].size();
	int cnt=sz-1;
	int& ret=dp[mode][v][ID[v][p]];
	ret=0;
	if(cnt==0){
		if(mode==1)ret = -1e9;
		return;
	}
	if(v==p)return;

	int id=ID[p][v];
	int c=path[p][id].c;
	int z=0;
	ret = sum[v] - max(dp[0][p][id],dp[1][p][id]+c);

	if(v!=root){
		id = ID[par[v]][v];
		c = path[par[v]][id].c;
		z = max(dp[0][par[v]][id],dp[1][par[v]][id]+c);
		ret += z;
		if(mode==1){
			if(Maxi[v][0]!=p){
				ret+=max(Max[v][0],dp[0][par[v]][id]+c-z);
			}else{
				ret+=max(Max[v][1],dp[0][par[v]][id]+c-z);
			}
		}
	}else{
		if(mode==1){
			if(Maxi[v][0]!=p){
				ret+=Max[v][0];
			}else{
				ret+=Max[v][1];
			}
		}
	}
}

void dfs2(int v,int p,int mode){

	int& ret=dp[mode][v][ID[v][p]];
	if(~ret)return;
	
	if(v==root){
		process2(v,p,mode);
		return;
	}

	dfs2(par[v],v,0);
	dfs2(par[v],v,1);
	if(v!=p)process2(v,p,mode);

//	printf("%d %d %d : %d\n",v,p,mode,dp[mode][v][ID[v][p]]);

}

int process3(int v){
	int ret=0;
	int sz=path[v].size();
	for(int i=0;i<sz;i++){
		int u=path[v][i].u;
		int c=path[v][i].c;
		int id=ID[u][v];
		int z = max(dp[0][u][id],dp[1][u][id]+c);
		ret+=z;
	}
	return ret;
}

void PS(){

	for(int i=1;i<=N;i++){
		for(int j=0;j<2;j++){
			Max[i][j]=-1e9;
		}
	}

	root=1;
	int ans=0;

	dfs(1,1,0);
	dfs(1,1,1);
	
	/*
	printf("%d\n",dp[0][1][ID[1][1]]);
	for(int i=1;i<=N;i++){
		printf("%d : %d / ",i,sum[i]);
		for(int j=0;j<2;j++){
			printf("%d(%d) ",Max[i][j],Maxi[i][j]);
		}
		puts("");
	}
*/

	for(int i=2;i<=N;i++){
		if(path[i].size()==1)dfs2(i,i,0);
	}

	for(int i=1;i<=N;i++){
		ans=max(ans,process3(i));
	}
	printf("%d\n",ans);

}

int main(){
	input();
	PS();
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int getMax(int, vec2&)':
beads.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++){
              ~^~~~~~~~~
beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:107:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<path[v].size();i++){
              ~^~~~~~~~~~~~~~~
beads.cpp: In function 'void input()':
beads.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
beads.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&x,&y,&z);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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