Submission #260526

#	Time	Username	Problem	Language	Result	Execution time	Memory
260526		shayan_p	Beads and wires (APIO14_beads)	C++14	0 / 100	4 ms	4992 KiB

beads

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 2e5 + 10, mod = 1e9 + 7;
const ll inf = 1e18 + 10;

vector<pii> v[maxn];
ll ans[maxn], dp[maxn];

void dfs(int u, int par = -1){
    ll mx1 = -inf, mx2 = -inf, sm = 0;
    for(auto [y, c] : v[u]){
	if(y != par){
	    dfs(y, u);
	    ll x = max(ans[y], dp[y] + c);
	    sm+= x;
	    x = ans[y] - x + c;
	    if(x > mx1)
		mx2 = mx1, mx1 = x;
	    else if(x > mx2)
		mx2 = x;
	}
    }
    dp[u] = sm + mx1;
    ans[u] = max(sm, sm + mx1 + mx2);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n;
    cin >> n;
    for(int i = 0; i < n-1; i++){
	int a, b, c;
	cin >> a >> b >> c;
	v[a].PB({b, c});
	v[b].PB({a, c});
    }
    dfs(1);
    return cout << ans[1] << endl, 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:24:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [y, c] : v[u]){
              ^

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