oj.uz

Submission #94601

# Submission time Handle Problem Language Result Execution time Memory
94601 2019-01-21T15:44:18 Z Alexa2001 Beads and wires (APIO14_beads) C++17
0 / 100
 8 ms 5120 KB 
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5, inf = 2e9 + 2;
typedef long long ll;

int dp[Nmax][4];
vector< pair<int,int> > v[Nmax];


void dfs(int node, int dad = 0)
{
    vector<int> zero, one, two;
    int up = 0, son, cost, i;

    for(auto it : v[node])
    {
        tie(son, cost) = it;
        if(son != dad)
        {
            dfs(son, node);
            zero.push_back(max(dp[son][0], dp[son][3]));
            one.push_back(dp[son][1]);
            two.push_back(dp[son][2]);
        }
        else up = cost;
    }

    /// case 0

    ll sum = 0;
    for(auto it : zero) sum += it;
    sum = max(sum, (ll)-inf);
    if(sum > dp[node][0]) dp[node][0] = sum;

    /// cases 1 & 2

    ll best = sum, best1 = -inf, best2 = -inf;
    for(i=0; i<zero.size(); ++i)
        best = max(best, sum - zero[i] + one[i]);

    for(i=0; i<zero.size(); ++i)
    {
        ll x = (ll) two[i] - zero[i];
        if(x >= best1) best2 = best1, best1 = x;
            else if(x > best2) best2 = x;
    }

    best = max(best, (ll)-inf);
    best1 = sum + best1 + best2;
    best1 = max(best1, (ll)-inf);

    dp[node][1] = dp[node][2] = max(best, best1);

    /// case 3

    best = -inf;
    for(i=0; i<zero.size(); ++i)
        best = max(best, sum - zero[i] + two[i]);

    dp[node][3] = best;


    ///
    dp[node][2] += up;
    dp[node][3] += up;
}

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

    int i, n, x, y, cost;
    cin >> n;
    for(i=1; i<=n; ++i) dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = -inf;

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

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

    return 0;
}

Compilation message

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

Subtask #1
0 / 13.0

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