Submission #84077

#	Time	Username	Problem	Language	Result	Execution time	Memory
84077		popovicirobert	Beads and wires (APIO14_beads)	C++14	0 / 100	6 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 = 1e13;
const int MAXN = (int) 2e5;

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

ll dp[MAXN + 1][2];

bool cmp(const pair <int, int> &a, const pair <int, int> &b) {
    return dp[a.first][0] + a.second - dp[a.first][1] >
           dp[b.first][0] + b.second - dp[b.first][1];
}

void dfs(int nod, int par, int cst) {
    vector < pair <int, int> > nodes;
    for(auto it : g[nod]) {
        if(it.first != par) {
            dfs(it.first, nod, it.second);
            nodes.push_back(it);
        }
    }
    sort(nodes.begin(), nodes.end(), cmp);
    vector <ll> new_dp(3);
    new_dp[1] = new_dp[2] = -INF;
    for(auto it : nodes) {
        vector <ll> cur(3);
        cur[0] = new_dp[0] + max(dp[it.first][1], dp[it.first][0]);
        cur[1] = max(new_dp[1] + max(dp[it.first][0], dp[it.first][1]), new_dp[0] + it.second + dp[it.first][0]);
        cur[2] = max(new_dp[2] + max(dp[it.first][0], dp[it.first][1]), new_dp[1] + it.second + dp[it.first][0]);
        new_dp = cur;
    }
    //new_dp[1] = max(new_dp[1], 0);
    dp[nod][0] = max(0LL, new_dp[2]);
    dp[nod][1] = -INF;
    if(new_dp[1] > 0) {
        dp[nod][1] = new_dp[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 << dp[1][0];
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message (stderr)

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

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