Submission #84083

#	Time	Username	Problem	Language	Result	Execution time	Memory
84083		popovicirobert	Beads and wires (APIO14_beads)	C++14	0 / 100	16 ms	5120 KiB

beads

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int INF = 1e12;
const int MAXN = (int) 2e5;

vector < pair <int, int> > g[MAXN + 1];

ll dp[MAXN + 1][3];
// dp[nod][0] = ai legat 2 fii
// dp[nod][1] = ai legat un fiu de tata
// dp[nod][2] = nu ai facut nimic

void dfs(int nod, int par, int cst) {
    dp[nod][0] = dp[nod][1] = -INF;
    for(auto it : g[nod]) {
        if(it.first != par) {
            dfs(it.first, nod, it.second);
            dp[nod][2] += max(dp[it.first][0], max(dp[it.first][1], dp[it.first][2]));
        }
    }
    ll new_dp[3][2];
    int i, j;
    for(i = 0; i < 3; i++) {
        for(j = 0; j < 2; j++) {
            new_dp[i][j] = -INF;
        }
    }
    new_dp[0][0] = 0;
    for(auto it : g[nod]) {
        if(it.first == par) {
            continue;
        }
        ll cur[3][2], val = max(dp[it.first][0], max(dp[it.first][1], dp[it.first][2]));
        cur[0][0] = new_dp[0][0] + val;
        cur[1][0] = max(new_dp[1][0] + val, new_dp[0][0] + dp[it.first][2] + it.second);
        cur[1][1] = max(new_dp[1][1] + val, new_dp[0][0] + dp[it.first][0] + it.second);
        cur[2][0] = max(new_dp[2][0] + val, new_dp[1][0] + dp[it.first][2] + it.second);
        cur[2][1] = max(new_dp[2][1] + val, max(new_dp[1][0] + dp[it.first][0], new_dp[1][1] + dp[it.first][2]) + it.second);
        for(i = 0; i < 3; i++) {
            for(j = 0; j < 2; j++) {
                new_dp[i][j] = cur[i][j];
            }
        }
    }
    dp[nod][0] = max(new_dp[2][0], new_dp[2][1]);
    dp[nod][1] = max(new_dp[1][0], new_dp[1][1]) + cst;
    //cerr << nod << " " << dp[nod][0] << " " << dp[nod][1] << "\n";
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin >> n;
    for(i = 1; i < n; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }
    dfs(1, 0, 0);
    cout << max(dp[1][0], dp[1][2]);
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message (stderr)

beads.cpp:10:17: warning: overflow in implicit constant conversion [-Woverflow]
 const int INF = 1e12;
                 ^~~~

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