oj.uz

Submission #145212

# Submission time Handle Problem Language Result Execution time Memory
145212 2019-08-19T09:45:27 Z dolphingarlic Beads and wires (APIO14_beads) C++14
0 / 100
 6 ms 5112 KB 
#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#define FOR(i, x, y) for (ll i = x; i < y; i++)
#define x first
#define y second
typedef long long ll;
using namespace std;

vector<pair<ll, ll>> graph[200001];
ll dp[200001][4];

void dfs(ll node, ll parent, ll edge) {
    ll best = INT_MIN, second = INT_MIN;

    for (pair<ll, ll> i : graph[node]) {
        if (i.x != parent) {
            dfs(i.x, node, i.y);
            dp[node][0] += max(max(dp[i.x][0], dp[i.x][1]), max(dp[i.x][2], dp[i.x][3]));
        }
    }
    for (pair<ll, ll> i : graph[node]) {
        if (i.x != parent) {
            dp[node][2] = max(dp[node][2], dp[node][0] - max(max(dp[i.x][0], dp[i.x][1]), max(dp[i.x][2], dp[i.x][3])) + dp[i.x][0] + i.second + edge);
            dp[node][2] = max(dp[node][2], dp[node][0] - max(max(dp[i.x][0], dp[i.x][1]), max(dp[i.x][2], dp[i.x][3])) + dp[i.x][1] + i.second + edge);

            if (max(dp[i.x][0], dp[i.x][1]) + i.second - max(max(dp[i.x][0], dp[i.x][1]), max(dp[i.x][2], dp[i.x][3])) > best) {
                second = best;
                best = max(dp[i.x][0], dp[i.x][1]) + i.second - max(max(dp[i.x][0], dp[i.x][1]), max(dp[i.x][2], dp[i.x][3]));
            } else if (max(dp[i.x][0], dp[i.x][1]) + i.second - max(max(dp[i.x][0], dp[i.x][1]), max(dp[i.x][2], dp[i.x][3])) > second) {
                second = max(dp[i.x][0], dp[i.x][1]) + i.second - max(max(dp[i.x][0], dp[i.x][1]), max(dp[i.x][2], dp[i.x][3]));
            }
        }
    }
    dp[node][1] = dp[node][0] + best + second;
}

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >> n;
    FOR(i, 1, n) {
        ll a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    dfs(1, 0, 0);

    cout << max(dp[1][0], dp[1][1]) << '\n';
    return 0;
}

Compilation message

beads.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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