oj.uz

Submission #84285

# Submission time Handle Problem Language Result Execution time Memory
84285 2018-11-14T08:54:22 Z Alexa2001 Beads and wires (APIO14_beads) C++17
0 / 100
 10 ms 9856 KB 
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5;

int up[Nmax], dp[Nmax][2], best[Nmax];
vector<int> v[Nmax], c[Nmax];
int x, y, n, i, cost;


void dfs(int node, int dad = 0)
{
    int i;

    for(i=0; i<v[node].size(); ++i)
        if(v[node][i] != dad)
        {
            up[v[node][i]] = c[node][i];
            dfs(v[node][i], node);
        }

    int add1 = -1e9, add2 = -1e9, sum = 0;

    for(auto son : v[node])
        if(son != dad)
        {
            sum += best[son];
            int curr = up[son] - best[son] + dp[son][0];
            if(curr >= add1) add2 = add1, add1 = curr;
                else if(curr > add2) add2 = curr;
        }

    dp[node][0] = max(sum, sum + add1 + add2);
    dp[node][1] = add1 + sum + up[node];

    best[node] = max(dp[node][0], dp[node][1]);
}

int main()
{
   // freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> n;
    for(i=1; i<n; ++i)
    {
        cin >> x >> y >> cost;
        v[x].push_back(y);
        v[y].push_back(x);
        c[x].push_back(cost);
        c[y].push_back(cost);
    }

    dfs(1);
    cout << dp[1][0] << '\n';

    return 0;
}

Compilation message

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v[node].size(); ++i)
              ~^~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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