Submission #19171

#	Time	Username	Problem	Language	Result	Execution time	Memory
19171		comet	Beads and wires (APIO14_beads)	C++14	28 / 100	1086 ms	14584 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;

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);
	}
}

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;
	}

	vec 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);
		ret+=z;
		if(mode==1){
			a.pb(dp[0][u][id]+c-z);
		}
	}
	
	if(mode==1){ // mode==1
		ret+=*max_element(a.begin(),a.end());
	}
}

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

	int& ret=dp[mode][v][ID[v][p]];
	if(~ret)return;
	
	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);
}

void PS(){

	int ans=0;
	for(int i=1;i<=N;i++){
		root=i;
		dfs(i,i,0);
		ans=max(ans,dp[0][i][ID[i][i]]);
	}
	printf("%d\n",ans);

}

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

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:80: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:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
beads.cpp:32: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: 0 / 29
• Subtask 4: 0 / 43