Submission #670174

#	Time	Username	Problem	Language	Result	Execution time	Memory
670174		Mahdi	Beads and wires (APIO14_beads)	C++17	100 / 100	259 ms	24448 KiB

beads

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=2e5+5;
int n, a[N], b[N], c[N], d[N], py[N];
vector<pii>g[N];

void dfs(const int &v, const int &p=-1){
    for(pii u: g[v]){
        if(u.F!=p){
            py[u.F]=u.S;
            dfs(u.F, v);
            d[v]+=c[u.F];
        }
    }
    b[v]=c[v]=d[v];
    int w=0, x=-2e9, y=-2e9, z=-2e9;
    for(pii u: g[v]){
        if(u.F!=p){
            c[v]=max(c[v], d[v]-c[u.F]+d[u.F]+u.S+py[v]);
            b[v]=max(b[v], d[v]-c[u.F]+a[u.F]);
            a[v]=max(a[v], d[v]-c[u.F]+b[u.F]+u.S+py[v]);
            z=max({z+c[u.F], y+d[u.F]+u.S, x+b[u.F]+u.S});
            y=max(y+c[u.F], w+b[u.F]+u.S);
            x=max(x+c[u.F], w+d[u.F]+u.S);
            w+=c[u.F];
        }
    }
    b[v]=max(b[v], z);
    a[v]=max({a[v], b[v], y+py[v]});
}

int main(){
    cin>>n;
    for(int i=1;i<n;++i){
        int u, v, w;
        cin>>u>>v>>w;
        g[--u].push_back({--v, w});
        g[v].push_back({u, w});
    }
    py[0]=-2e9;
    dfs(0);
    cout<<a[0]<<'\n';
}

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