oj.uz

Submission #84087

# Submission time Handle Problem Language Result Execution time Memory
84087 2018-11-12T20:11:02 Z popovicirobert Beads and wires (APIO14_beads) C++17
0 / 100
 6 ms 5120 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 ll 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) {
    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(-INF, max(new_dp[2][0], new_dp[2][1]));
    dp[nod][1] = max(-INF, 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

beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:47:40: warning: 'cur[0][1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 new_dp[i][j] = cur[i][j];
                                ~~~~~~~~^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 5 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Incorrect 6 ms 5120 KB Output isn't correct
8 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 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 5 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Incorrect 6 ms 5120 KB Output isn't correct
8 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 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 5 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Incorrect 6 ms 5120 KB Output isn't correct
8 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 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 5 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Incorrect 6 ms 5120 KB Output isn't correct
8 Halted 0 ms 0 KB -