oj.uz

Submission #732799

# Submission time Handle Problem Language Result Execution time Memory
732799 2023-04-29T10:05:40 Z vjudge1 Beads and wires (APIO14_beads) C++17
0 / 100
 1 ms 304 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
        int n;
        cin >> n;
        if (n <= 2) return cout << 0, 0;
        vector<vector<pair<int, int>>> adj(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);
        }
        vector<vector<int>> g(2, vector<int>(n, 0));
        function<void(int, int)> dfs = [&](int u, int p) {
                g[0][u] = 0;
                g[1][u] = -1e9;
                for (pair<int, int>& e : adj[u]) {
                        int v = e.first;
                        int c = e.second;
                        if (v == p) continue;
                        dfs(v, u);
                        g[0][u] += max(g[0][v], g[1][v] + c);
                }

                vector<int> best;
                for (pair<int, int>& e : adj[u]) {
                        int v = e.first;
                        int c = e.second;
                        if (v == p) continue;
                        g[1][u] = max(g[1][u], g[0][u] - max(g[0][v], g[1][v] + c) + (g[0][v] + c));
                        best.emplace_back(g[0][v] + c - max(g[0][v], g[1][v] + c));
                        int j = best.size() - 1;
                        while (j > 0 && best[j] > best[j - 1]) swap(best[j], best[j - 1]), j--;
                        if (best.size() > 2) best.pop_back();
                }
                if (best.size() == 2) g[0][u] += max(0, best[0] + best[1]);
        };
        int res = 0;
        for (int i = 0; i < n; i++) dfs(i, -1), res = max(res, g[0][i]);
        cout << res;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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