Submission #260577

#	Time	Username	Problem	Language	Result	Execution time	Memory
260577		shayan_p	Beads and wires (APIO14_beads)	C++17	100 / 100	282 ms	33656 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[2][maxn], dp[2][maxn]; // 0 up 1 down

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

	    dp[1][u]+= x;
	    mx2 = max(mx2, c + ans[1][y] - x);
	}
    }
    dp[0][u]+= mx1;
    dp[1][u]+= mx2;
	
    ll sm = 0;
    ll mx = -inf;

    vector<pair<ll, int> > v1, v2;
    for(auto [y, c] : v[u]){
	if(y != par){
	    ll x = max(ans[0][y], dp[0][y] + c);
	    sm+= x;
	    mx = max(mx, max(dp[1][y] + c, ans[1][y]) -x);
	    v1.PB({ans[1][y] + c - x, y});
	    v2.PB({ans[0][y] + c - x, y});
	}
    }
    sort(v1.begin(), v1.end());
    reverse(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    reverse(v2.begin(), v2.end());
    for(int i = 0; i < min(2, sz(v1)); i++)
	for(int j = 0; j < min(2, sz(v2)); j++)
	    if(v1[i].S != v2[j].S)
		ans[1][u] = max(ans[1][u], sm + v1[i].F + v2[j].F);
    ans[1][u] = max(ans[1][u], sm + mx);
    ans[1][u] = max(ans[1][u], ans[0][u]);
}

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][1] << endl, 0;
}

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