Submission #992552

#	Time	Username	Problem	Language	Result	Execution time	Memory
992552		star	Beads and wires (APIO14_beads)	C++17	28 / 100	1068 ms	8796 KiB

beads

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define starburst ios::sync_with_stdio(0), cin.tie(0)
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(),x.end()
#define inf 0x3f3f3f3f
#define N 200005
int n, a, b, c, ans=0;
vector<pii> adj[N];
int in[N], ex[N];
void dfs(int v, int parent){
    int sum=0, pw=-inf;
    for (auto it:adj[v]){
        int u=it.F;
        if (u==parent) {pw=it.S;continue;}
        dfs(u,v);
        sum+=in[u];
    }
    in[v]=ex[v]=sum;
    for (auto it:adj[v]){
        int u=it.F;
        if (u==parent) continue;
        in[v]=max(in[v], sum-in[u]+ex[u]+pw+it.S);
    }
}
signed main(){
    starburst;
    cin >> n;
    for (int i=0;i<n-1;i++){
        cin >> a >> b >> c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }
    for (int v=1;v<=n;v++){
//        memset(x,0,sizeof(in));
//        memset(y,0,sizeof(ex));
        for (int i=1;i<=n;i++) in[i]=ex[i]=0;
        dfs(v,0);
        //dfs(v);
        ans=max(ans, in[v]);
    }
    cout << ans;
    return 0;
}

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