Submission #980883

#	Time	Username	Problem	Language	Result	Execution time	Memory
980883		Ivo_12	Beads and wires (APIO14_beads)	C++11	13 / 100	6 ms	21432 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 = 2e5+10;
int n;
vector < pll > edges[N];
vector < pll > takea[N];
vector < pll > takeb[N];
vector < ll > takec[N];
ll dp[N][4]; // dp[x][0] - nastavak ne T-a, dp[x][1] - nastavak T-a ili pocetak T-a, dp[x][2] - nista se ne nastavlja, dp[x][3] - nastavak T-a prema parentu

void dfs( int pos, int par ) {
	
	ll total = 0, parval = -1e9, jedan = -1e9, dva = -1e9, nastavakt = -1e9, nastavaktp = -1e9, total2 = 0;
	for(int i = 0; i < (int) edges[pos].size(); i++) {
		if(edges[pos][i].f!=par) {
			dfs(edges[pos][i].f, pos);
			total += max(dp[edges[pos][i].f][0], dp[edges[pos][i].f][2]);
			total2 += max(max(dp[edges[pos][i].f][0], dp[edges[pos][i].f][2]), dp[edges[pos][i].f][1]);
			takea[pos].pb(mp(dp[edges[pos][i].f][2] - max(dp[edges[pos][i].f][0], dp[edges[pos][i].f][2]) + edges[pos][i].s, edges[pos][i].f));
			takeb[pos].pb(mp(dp[edges[pos][i].f][1] - max(dp[edges[pos][i].f][0], dp[edges[pos][i].f][2]) + edges[pos][i].s, edges[pos][i].f));
			takec[pos].pb(dp[edges[pos][i].f][3] - max(dp[edges[pos][i].f][0], dp[edges[pos][i].f][2]));
		}
		else parval = edges[pos][i].s;
	}
	sort(takea[pos].begin(), takea[pos].end());
	reverse(takea[pos].begin(), takea[pos].end());
	sort(takeb[pos].begin(), takeb[pos].end());
	reverse(takeb[pos].begin(), takeb[pos].end());
	sort(takec[pos].begin(), takec[pos].end());
	reverse(takec[pos].begin(), takec[pos].end());
	
	if((int) takea[pos].size() > 0) jedan = parval + takea[pos][0].f;
	if((int) takea[pos].size() > 1) dva = takea[pos][1].f + takea[pos][0].f;
	if((int) takea[pos].size() > 1 && takea[pos][0].s != takeb[pos][0].s) nastavakt = takea[pos][0].f + takeb[pos][0].f;
	if((int) takea[pos].size() > 1 && takea[pos][0].s == takeb[pos][0].s) nastavakt = max(takea[pos][0].f + takeb[pos][1].f, takea[pos][1].f + takeb[pos][0].f);
	if((int) takec[pos].size() > 0) nastavaktp = takec[pos][0];
	dp[pos][2] = total2;
	dp[pos][0] = total + jedan;
	dp[pos][1] = total + max(max(dva, nastavakt), nastavaktp);
	if((int) takeb[pos].size() > 0) dp[pos][3] = total + parval + takeb[pos][0].f;
	else dp[pos][3] = -1e9;
	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 << max(dp[0][0], max(dp[0][1], dp[0][2])) << "\n";
	
	return 0;
}

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