Submission #19176

#	Time	Username	Problem	Language	Result	Execution time	Memory
19176		comet	Beads and wires (APIO14_beads)	C++14	57 / 100	1087 ms	79096 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;
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});
	}
	for(int i=1;i<=N;i++){
		int sz=path[i].size();
		ID[i][i]=sz;
		dp[0][i].resize(sz+1,-1);
		dp[1][i].resize(sz+1,-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 sz=path[v].size();
	int cnt=sz-(v!=root);
	int& ret0=dp[0][v][ID[v][p]];
	int& ret1=dp[1][v][ID[v][p]];
	if(cnt==0){
		ret0=0;
		ret1=-1e9;
		return;
	}

	vec2 a;
	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;
		a.pb(pt{u,dp[0][u][id]+c-z});
	}

	ret0=ret1=sum[v];
	ret1+=getMax(v,a);
}

void dfs(int v,int p){

	int& ret=dp[0][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);
	}
	
	process(v,p);
}

void process2(int v,int p){
	int sz=path[v].size();
	int cnt=sz-1;
	int& ret0=dp[0][v][ID[v][p]];
	int& ret1=dp[1][v][ID[v][p]];

	if(cnt==0){
		ret0 = 0;
		ret1 = -1e9;
		return;
	}
	if(v==p)return;

	int id=ID[p][v];
	int c=path[p][id].c;
	int z=0;
	ret0 = ret1 = 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);
		ret0 += z;
		ret1 += z;
		if(Maxi[v][0]!=p){
			ret1+=max(Max[v][0],dp[0][par[v]][id]+c-z);
		}else{
			ret1+=max(Max[v][1],dp[0][par[v]][id]+c-z);
		}
	}else{
		if(Maxi[v][0]!=p){
			ret1+=Max[v][0];
		}else{
			ret1+=Max[v][1];
		}
	}
}

void dfs2(int v,int p){

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

	dfs2(par[v],v);
	if(v!=p)process2(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(){

	root=1;
	int ans=0;

	dfs(1,1);

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

	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:53: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)':
beads.cpp:101: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:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
beads.cpp:36: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