Submission #980096

#	Time	Username	Problem	Language	Result	Execution time	Memory
980096		Ivo_12	Beads and wires (APIO14_beads)	C++11	0 / 100	5 ms	21084 KiB

beads

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

using namespace std;

const int N = 4e5+10;
int n;
vector < pll > edges[N];
vector < ll > takeb[N];
pll nastavi[N];

void dfs( int pos, int par ) {
	
	ll paran = 0, neparan = -1e9, total = 0, parval = 0;
	for(int i = 0; i < (int) edges[pos].size(); i++) {
		if(edges[pos][i].f != par) {
			dfs(edges[pos][i].f, pos);
			total += nastavi[edges[pos][i].f].f;
			takeb[pos].pb(nastavi[edges[pos][i].f].s - nastavi[edges[pos][i].f].f + edges[pos][i].s);
		}
		else parval = edges[pos][i].s;
	}
	sort(takeb[pos].begin(), takeb[pos].end());
	reverse(takeb[pos].begin(), takeb[pos].end());
	
	if((int) takeb[pos].size() > 0) neparan = takeb[pos][0];
	if((int) takeb[pos].size() > 1) paran = max((ll) 0, takeb[pos][0] + takeb[pos][1]);
	nastavi[pos].f = total + max(paran, neparan + parval);
	nastavi[pos].s = total + paran;
	return;
	
}

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

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