Submission #198675

#	Time	Username	Problem	Language	Result	Execution time	Memory
198675		gs18081	Beads and wires (APIO14_beads)	C++11	100 / 100	285 ms	32236 KiB

beads

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pi;
typedef long long int ll;
	
const int MAXN = 202020;
const ll MAX = 2e9;

vector<pi> edge[MAXN];
ll plen[MAXN];
ll dp1[MAXN];
ll dp2[MAXN];
ll dp3[MAXN];
ll dp4[MAXN];
int N;

void dfs(int node,int par){
	ll mx2 = -MAX;
	ll mx4 = -MAX;
	vector<pi> vect3;
	int ccnt = 0;
	for(auto i : edge[node]){
		if(i.first == par) continue;
		ccnt++;
		plen[i.first] = i.second;
		dfs(i.first,node);
		dp1[node] += max(dp1[i.first] , dp2[i.first]);
		mx2 = max(mx2 , dp1[i.first] + plen[i.first] - max(dp1[i.first],dp2[i.first])); 
		mx4 = max(mx4 , dp3[i.first] + plen[i.first] - max(dp1[i.first],dp2[i.first])); 
		vect3.push_back(pi(dp1[i.first] + plen[i.first] - max(dp1[i.first],dp2[i.first]), i.first));
	}
	sort(vect3.begin(),vect3.end(),greater<pi>());
	dp2[node] = dp1[node] + mx2 + plen[node];
	dp4[node] = dp1[node] + mx4 + plen[node];
	dp3[node] = dp1[node];
	if(ccnt > 1){
		for(auto i : edge[node]){
			if(i.first == par) continue;
			int j;
			for(j = 0;j<vect3.size();j++){
				if(i.first != vect3[j].second) break;
			}
			if(j == vect3.size()) continue;
			dp3[node] = max(dp3[node] , dp1[node] + dp3[i.first] + plen[i.first] - max(dp1[i.first] , dp2[i.first]) + vect3[j].first);
		}
	}
	for(auto i : edge[node]){
		if(i.first == par) continue;
		dp3[node] = max(dp3[node] , dp1[node] + dp3[i.first] - max(dp1[i.first] , dp2[i.first]));
		dp3[node] = max(dp3[node] , dp1[node] + dp4[i.first] - max(dp1[i.first] , dp2[i.first]));
	}
	assert(dp4[node] >= dp2[node]);
//	printf("%d %lld %lld %lld %lld\n",node,dp1[node],dp2[node],dp3[node],dp4[node]);


	

}



int main(){
	scanf("%d",&N);
	for(int i=1;i<N;i++){
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		edge[a].push_back(pi(b,c));
		edge[b].push_back(pi(a,c));
	}
	dfs(1,1);
	printf("%lld\n",max(dp1[1],dp3[1]));
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j = 0;j<vect3.size();j++){
              ~^~~~~~~~~~~~~
beads.cpp:45:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(j == vect3.size()) continue;
       ~~^~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
beads.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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