Submission #981156

#	Time	Username	Problem	Language	Result	Execution time	Memory
981156		Ivo_12	Beads and wires (APIO14_beads)	C++98	100 / 100	214 ms	62436 KiB

beads

#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define pll pair < ll, ll >

using namespace std;

const int N = 2e5+10;
int n;
vector < pll > edges[N];
int deg[N];
int root;
ll dp[N][2][2]; //dp[x][y][z], x = node, y = (1 - able to connect) (0 - unable to connect), z = okomica nadena ili nije
vector < pll > spoji1[N];
vector < pll > spoji2[N];
vector < pll > spoji3[N];
ll sol = 0;

void dfs(int pos, int par) {
	ll parval = -1e9, total = 0, dolje = -1e9, dvadolje = -1e9, doljesokomitim = -1e9, najveciokomiti = -1e9, dvadoljeijedanok = -1e9;
	for(int i = 0; i < (int) edges[pos].size(); i++) {
		if(edges[pos][i].f != par) {
			dfs(edges[pos][i].f, pos);
			total += dp[edges[pos][i].f][0][0];
			spoji1[pos].pb(mp(dp[edges[pos][i].f][1][0] - dp[edges[pos][i].f][0][0] + edges[pos][i].s, edges[pos][i].f));
			spoji2[pos].pb(mp(dp[edges[pos][i].f][0][1] - dp[edges[pos][i].f][0][0], edges[pos][i].f));
			spoji3[pos].pb(mp(dp[edges[pos][i].f][1][1] - dp[edges[pos][i].f][0][0] + edges[pos][i].s, edges[pos][i].f));
		}
		else parval = edges[pos][i].s;
	}
	sort(spoji1[pos].begin(), spoji1[pos].end()); reverse(spoji1[pos].begin(), spoji1[pos].end());
	sort(spoji2[pos].begin(), spoji2[pos].end()); reverse(spoji2[pos].begin(), spoji2[pos].end());
	sort(spoji3[pos].begin(), spoji3[pos].end()); reverse(spoji3[pos].begin(), spoji3[pos].end());
	
	if((int) spoji1[pos].size()>0) dolje = spoji1[pos][0].f;
	if((int) spoji1[pos].size()>1) dvadolje = spoji1[pos][0].f + spoji1[pos][1].f;
	if((int) spoji2[pos].size()>0) doljesokomitim = spoji2[pos][0].f;
	if((int) spoji3[pos].size()>0) najveciokomiti = spoji3[pos][0].f;
	if((int) spoji3[pos].size()>1) {
		if(spoji1[pos][0].s!=spoji3[pos][0].s) dvadoljeijedanok = spoji1[pos][0].f + spoji3[pos][0].f;
		else dvadoljeijedanok = max(spoji1[pos][0].f + spoji3[pos][1].f, spoji1[pos][1].f + spoji3[pos][0].f);
	}
	
	dp[pos][1][0] = total;
	dp[pos][0][0] = max(total, total + dolje + parval);
	dp[pos][1][1] = total + max(max(dvadolje, doljesokomitim), dvadoljeijedanok);
	dp[pos][0][1] = max(dp[pos][1][1], total + najveciokomiti + parval);
	
}

int main( void ) {
	
	FIO
	cin >> n;
	ll tempa, tempb, tempc;
	for(int i = 0; i < n-1; i++) {
		cin >> tempa >> tempb >> tempc;
		edges[--tempa].pb(mp(--tempb, tempc));
		edges[tempb].pb(mp(tempa, tempc));
		deg[tempa]++; deg[tempb]++;
	}
	
	dfs(0, -1);
	sol = max(sol, max(max(dp[root][0][0], dp[root][1][0]), max(dp[root][0][1], dp[root][1][1])));
	cout << sol;
	
	return 0;
}

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