Submission #369172

#	Time	Username	Problem	Language	Result	Execution time	Memory
369172		BartolM	Beads and wires (APIO14_beads)	C++17	100 / 100	282 ms	22240 KiB

beads

#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];
int dp[N][2];

int rek(int node, int fl, int par) {
    int &ret=dp[node][fl];
    if (ret!=-1) return ret;

    int sum0=0, ed;
    for (pii sus:ls[node]) {
        if (sus.X==par) {
            ed=sus.Y;
            continue;
        }
        sum0+=rek(sus.X, 0, node);
    }
    ret=sum0;
    for (pii sus:ls[node]) {
        if (sus.X==par) continue;
        if (!fl) ret=max(ret, ed+sus.Y+sum0-rek(sus.X, 0, node)+rek(sus.X, 1, node));
    }
    return ret;
}

void pokreni(int node, int par) {
    rek(node, 0, par);
    rek(node, 1, par);
    for (pii sus:ls[node]) if (sus.X!=par) pokreni(sus.X, node);
}

int dfs(int node, int par, int val0, int val1) {
    int sum0=val0, ed=0;
    for (pii sus:ls[node]) {
        if (sus.X==par) {
            ed=sus.Y;
            continue;
        }
        sum0+=dp[sus.X][0];
    }
    int ret=sum0;
    int maxi[2]={sum0+ed-val0+val1, 0};
    if (!par) maxi[0]=0;
    for (pii sus:ls[node]) {
        if (sus.X==par) continue;

        int x=sum0+sus.Y-dp[sus.X][0]+dp[sus.X][1];
        for (int i=0; i<2; ++i) if (x>maxi[i]) swap(x, maxi[i]);
    }

    int p0, p1=sum0;
    for (pii sus:ls[node]) {
        if (sus.X==par) continue;
        int curr=sum0+sus.Y-dp[sus.X][0]+dp[sus.X][1];

        if (maxi[0]==curr) p0=maxi[1]+sus.Y-dp[sus.X][0];
        else p0=maxi[0]+sus.Y-dp[sus.X][0];
        ret=max(ret, dfs(sus.X, node, max(p1-dp[sus.X][0], p0), p1-dp[sus.X][0]));
    }
    return ret;
}

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();
    memset(dp, -1, sizeof dp);
    pokreni(1, 0);
    int p[2]={0, 0};
    printf("%d\n", dfs(1, 0, 0, 0));
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:94:9: warning: unused variable 'p' [-Wunused-variable]
   94 |     int p[2]={0, 0};
      |         ^
beads.cpp: In function 'void load()':
beads.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
beads.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |         scanf("%d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp: In function 'int rek(int, int, int)':
beads.cpp:38:33: warning: 'ed' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |         if (!fl) ret=max(ret, ed+sus.Y+sum0-rek(sus.X, 0, node)+rek(sus.X, 1, node));
      |                                 ^

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