oj.uz

Submission #258958

# Submission time Handle Problem Language Result Execution time Memory
258958 2020-08-06T21:07:05 Z DS007 Beads and wires (APIO14_beads) C++14
0 / 100
 4 ms 4992 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2e5;
vector<pair<int, int>> adj[N];
int dp1[N], dp2[N], n;

void dfs(int v, int p = -1) {
    vector<int> v1, v2, v3;
    int ans = 0, delta = -1e18;

    for (auto i : adj[v]) {
        if (i.first == p)
            continue;

        dfs(i.first, v);
        v1.push_back(dp1[i.first]);
        v2.push_back(dp2[i.first] + i.second);

        ans += max(v1.back(), v2.back());
        if (v1.back() >= v2.back())
            v3.push_back(i.second);
        else
            v3.push_back(dp1[i.first] - dp2[i.first]);
    }

    dp1[v] = ans;
    sort(v3.begin(),v3.end(), greater<>());
    if (v3.size() >= 2 && v3[0] + v3[1] > 0)
        dp1[v] += v3[0] + v3[1];

    dp2[v] = ans + (v3.empty() ? -1e18 : v3[0]);
}

int solveTestCase() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }

    dfs(0);
    cout << dp1[0];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--)
        solveTestCase();
}

Compilation message

beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:11:18: warning: unused variable 'delta' [-Wunused-variable]
     int ans = 0, delta = -1e18;
                  ^~~~~
beads.cpp: In function 'long long int solveTestCase()':
beads.cpp:48:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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