oj.uz

Submission #84076

# Submission time Handle Problem Language Result Execution time Memory
84076 2018-11-12T19:18:00 Z popovicirobert Beads and wires (APIO14_beads) C++14
0 / 100
 6 ms 4992 KB 
#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 = 2e9;
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 a.second > b.second;
}

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 <int> new_dp(3);
    new_dp[1] = new_dp[2] = -INF;
    for(auto it : nodes) {
        vector <int> cur(3);
        cur[0] = new_dp[0] + max(dp[it.first][1], dp[it.first][0]);
        cur[1] = max(new_dp[1] + 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);
    new_dp[2] = max(new_dp[2], 0);
    dp[nod][0] = 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;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Incorrect 6 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Incorrect 6 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Incorrect 6 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Incorrect 6 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -