Submission #22070

#	Time	Username	Problem	Language	Result	Execution time	Memory
22070		amsen	Beads and wires (APIO14_beads)	C++11	13 / 100	11 ms	5120 KiB

beads

//in the name of allah
#include<vector>
#include<iostream>
#include<map>
#include<bitset>
#include<algorithm>
#include<set>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 2e5+1 , inf = 1e9;
typedef pair<int , int> ii;
int dpr[maxn] , dpe[maxn] , dp[maxn] , dpt[maxn] , n;
vector<ii> g[maxn];
void dfs(int v , int par){
	dpe[v] = -1e9;
	dpt[v] = -1e9;
	int sum=0;
	set<ii> st;
	for(auto U : g[v]){
		int u = U.first , w = U.second;
		if(u == par)
			continue;
		dfs(u , v);
		int cur = max(dpe[u] + w , dp[u]);
		sum += cur;
		st.insert(ii(w+dpr[u]-cur , u));
	}
	dpr[v] = sum;
	dp[v] = dpr[v];
	for(auto U : g[v]){
		int u = U.first , w = U.second;
		if(u == par)
			continue;
		int cur = max(dpe[u] + w , dp[u]);
		dpt[v] = max(dpt[v] , sum - cur + w + dp[u]);
		dpe[v] = max(dpe[v] , sum - cur + w + dpr[u]);
		st.erase(ii(w+dpr[u]-cur , u));
		if((int)st.size())
			dp[v] = max(dp[v] , dp[u] + w + sum - cur + st.rbegin()->first);
		dp[v] = max(dp[v] , dpt[u] + w + sum - cur);
		st.insert(ii(w+dpr[u]-cur , u));
	}
}

int main(){
	scanf("%d" , &n);
	for(int i=0 ; i<n-1 ; i++){
		int v , u , w;
		scanf("%d%d%d" , &v , &u , &w);
		v --;
		u --;
		g[v].push_back(ii(u , w));
		g[u].push_back(ii(v , w));
	}
	dfs(0 , -1);
	printf("%d\n" , dp[0]);
}
/*
10
4 10 2 1 2 21 1 3 13 6 7 1 7 9 5 2 4 3 2 5 8 1 6 55 6 8 34
*/

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &n);
  ~~~~~^~~~~~~~~~~
beads.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d" , &v , &u , &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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