oj.uz

Submission #363791

# Submission time Handle Problem Language Result Execution time Memory
363791 2021-02-07T09:28:45 Z BartolM Beads and wires (APIO14_beads) C++17
0 / 100
 4 ms 4972 KB 
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const ll MAX=(ll)INF*INF;
const int N=2e5+5;

int n;
vector <pii> ls[N];
ll dp[N][2];

void rek(int node, int fl, int par) {

    for (pii sus:ls[node]) {
        if (sus.X!=par) {
            rek(sus.X, 0, node);
            rek(sus.X, 1, node);
        }
    }
    ll maxi[2]={-MAX, -MAX};
    ll sum0=0;
    for (pii sus:ls[node]) {
        ll x;
        if (sus.X==par) {
            if (fl) continue;
            x=sus.Y;
        }
        else {
            sum0+=dp[sus.X][0];
            x=dp[sus.X][1]-dp[sus.X][0]+sus.Y;
        }
        for (int i=0; i<2; ++i) if (x>maxi[i]) swap(x, maxi[i]);
    }
    dp[node][fl]=max(sum0, sum0+maxi[0]+maxi[1]);
}

void load() {
    scanf("%d", &n);
    for (int i=0; i<n-1; ++i) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        ls[a].pb(mp(b, c));
        ls[b].pb(mp(a, c));
    }
}

int main() {
    load();
    rek(1, 1, 1);
    printf("%lld\n", dp[1][1]);
    return 0;
}

Compilation message

beads.cpp: In function 'void load()':
beads.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
beads.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         scanf("%d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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