Submission #231018

#	Time	Username	Problem	Language	Result	Execution time	Memory
231018		lyc	Beads and wires (APIO14_beads)	C++14	100 / 100	227 ms	27760 KiB

beads

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ii=pair<int,int>;
using ll=long long;

const int MX_N = 2e5+5;
const int INF = 2e9+10;

int N;
vector<ii> al[MX_N];

ll f[MX_N][3], g[MX_N][2], ans = 0;

void DFS(int u, int p) {
    ll best[] = {-INF,-INF};
    for (ii v : al[u]) if (v.first != p) {
        DFS(v.first,u);

        ll val = max(f[v.first][0], f[v.first][1]+v.second);
        f[u][0] += val;
        ll x = f[v.first][0]+v.second - val;
        FOR(i,0,1) if (x > best[i]) swap(x,best[i]);
    }
    if (best[0] == -INF) f[u][1] = -INF;
    else f[u][1] = f[u][0] + best[0];
    if (f[u][1] == -INF || best[1] == -INF) f[u][2] = -INF;
    else f[u][2] = f[u][1] + best[1];
    ans = max(ans, f[u][0]);
}

void DFS2(int u, int p) {
    ll sum = 0;
    ll best[] = {-INF,-INF};
    ll bestV[] = {-1,-1};
    for (ii v : al[u]) if (v.first != p) {
        ll val = max(f[v.first][0], f[v.first][1]+v.second);
        sum += val;
        ll x = f[v.first][0]+v.second - val;
        ll y = v.first;
        FOR(i,0,1) if (x > best[i]) swap(x,best[i]), swap(y,bestV[i]);
    }
    for (ii v : al[u]) if (v.first != p) {
        ll val = max(f[v.first][0], f[v.first][1]+v.second);
        g[v.first][0] = max({
                    g[u][0] + (sum-val),
                    v.second + g[u][1] + (sum-val),
                    v.second + g[u][0] + (sum-val) + (bestV[0] == v.first ? best[1] : best[0])
                });
        g[v.first][1] = v.second + g[u][0] + (sum-val),
        DFS2(v.first,u);
    }
    ans = max(ans, f[u][0] + g[u][0]);
    if (f[u][1] != -INF) ans = max(ans, f[u][1] + g[u][1]);
    if (f[u][2] != -INF) ans = max(ans, f[u][2] + g[u][0]);
    //TRACE(u _ g[u][0] _ g[u][1]);
    //TRACE(u _ f[u][0] _ f[u][1] _ f[u][2] _ g[u][0] _ g[u][1]);
}

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

    cin >> N;
    FOR(i,1,N-1){
        int A, B, C; cin >> A >> B >> C;
        al[A].emplace_back(B,C);
        al[B].emplace_back(A,C);
    }

    DFS(1,0);
    g[1][1] = -INF;
    DFS2(1,0);
    cout << ans;
}

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