oj.uz

Submission #107895

# Submission time Handle Problem Language Result Execution time Memory
107895 2019-04-26T07:46:38 Z SamAnd Beads and wires (APIO14_beads) C++17
0 / 100
 6 ms 5120 KB 
#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

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.0

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