Submission #107895

#	Time	Username	Problem	Language	Result	Execution time	Memory
107895		SamAnd	Beads and wires (APIO14_beads)	C++17	0 / 100	6 ms	5120 KiB

beads

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const long long INF = 20000000010;
struct ban
{
    int x, d;
    ban(){}
    ban(int x, int d)
    {
        this->x = x;
        this->d = d;
    }
};

int n;
vector<ban> a[N];

long long dp[N][2];

void dfs(int x, int p)
{
    for (int i = 0; i < a[x].size(); ++i)
    {
        ban h = a[x][i];
        if (h.x == p)
            continue;
        dfs(h.x, x);
    }
    long long sum = 0;
    for (int i = 0; i < a[x].size(); ++i)
    {
        ban h = a[x][i];
        if (h.x == p)
            continue;
        sum += max(dp[h.x][0], h.d + dp[h.x][1]);
    }
    dp[x][0] = sum;
    for (int i = 0; i < a[x].size(); ++i)
    {
        for (int j = i + 1; j < a[x].size(); ++j)
        {
            ban h1 = a[x][i];
            ban h2 = a[x][j];
            if (h1.x == p || h2.x == p)
                continue;
            sum -= max(dp[h1.x][0], h1.d + dp[h1.x][1]);
            sum -= max(dp[h2.x][0], h2.d + dp[h2.x][1]);
            dp[x][0] = max(dp[x][0], sum + h1.d + h2.d + dp[h1.x][0] + dp[h2.x][0]);
            sum += max(dp[h1.x][0], h1.d + dp[h1.x][1]);
            sum += max(dp[h2.x][0], h2.d + dp[h2.x][1]);
        }
    }
    if (x == 2)
        cout << "";
    dp[x][1] = -INF;
    for (int i = 0; i < a[x].size(); ++i)
    {
        ban h = a[x][i];
        if (h.x == p)
            continue;
        sum -= max(dp[h.x][0], h.d + dp[h.x][1]);
        dp[x][1] = max(dp[x][1], sum + h.d + dp[h.x][0]);
        sum += max(dp[h.x][0], h.d + dp[h.x][1]);
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        int x, y, d;
        cin >> x >> y >> d;
        a[x].push_back(ban(y, d));
        a[y].push_back(ban(x, d));
    }
    dfs(1, -1);
    cout << dp[1][0] << endl;
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:23:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
beads.cpp:31:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
beads.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
beads.cpp:41:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i + 1; j < a[x].size(); ++j)
                             ~~^~~~~~~~~~~~~
beads.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~

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