Submission #30156

#	Time	Username	Problem	Language	Result	Execution time	Memory
30156		Andrei1998	Beads and wires (APIO14_beads)	C++14	100 / 100	320 ms	23128 KiB

beads

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 200000 + 5;
const int INF = 2E9 + 15;

int N;
vector <pair <int, int> > graph[NMAX];
int fatherEdgeCost[NMAX];

int dp[NMAX][2];
void dfs1(int node, int father) {
    dp[node][0] = 0;
    dp[node][1] = -INF;
    for (auto it: graph[node])
        if (it.first != father) {
            dfs1(it.first, node);
            int val = max(dp[it.first][0], dp[it.first][1] + it.second);
            dp[node][0] += val;
            dp[node][1] = max(dp[node][1], it.second + dp[it.first][0] - val);
        }
    dp[node][1] = dp[node][0] + dp[node][1];
}

int ans;
int getBestNotNode(const vector <pair <int, int> > &v, int node) {
    for (int i = 0; i < v.size(); ++ i)
        if (v[i].second != node)
            return v[i].first;
    return -INF;
}

int up[NMAX][2];
void dfs2(int node, int father, int edge) {
    int cost = dp[node][0] + max(up[node][0], up[node][1] + edge);
    ans = max(ans, cost);

    vector <pair <int, int> > v;
    if (father)
        v.push_back(make_pair(up[node][0] + edge - max(up[node][0], up[node][1] + edge), father));

    for (auto it: graph[node])
        if (it.first != father) {
            int val = max(dp[it.first][0], dp[it.first][1] + it.second);
            up[it.first][0] = dp[node][0] - val + max(up[node][0], up[node][1] + edge);
            v.push_back(make_pair(it.second + dp[it.first][0] - val, it.first));
        }

    sort(v.begin(), v.end(), greater <pair <int, int> >());
    if (v.size() > 2)
        v.resize(2);

    for (auto it: graph[node])
        if (it.first != father) {
            int val = max(dp[it.first][0], dp[it.first][1] + it.second);
            up[it.first][1] = cost + getBestNotNode(v, it.first) - val;
        }
    for (auto it: graph[node])
        if (it.first != father)
            dfs2(it.first, node, it.second);
}

int main()
{
    //freopen("data.in", "r", stdin);
    ios_base :: sync_with_stdio(false);

    cin >> N;
    for (int i = 1; i < N; ++ i) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }

    dfs1(1, 0);
    dfs2(1, 0, 0);

    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int getBestNotNode(const std::vector<std::pair<int, int> >&, int)':
beads.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++ i)
                     ~~^~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43