Submission #260708

#	Time	Username	Problem	Language	Result	Execution time	Memory
260708		evpipis	Beads and wires (APIO14_beads)	C++11	0 / 100	3 ms	4992 KiB

beads

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;

const int len = 2e5+5, inf = 2e9+5;
int dp[len][2];
ii par[len];
vector<ii> adj[len];

/*
int solve(int u, int t){
    if (dp[u][t] != -1)
        return dp[u][t];

    int ans = 0, mx1 = -inf, mx2 = -inf;
    for (int j = 0; j < adj[u].size(); j++){
        ii v = adj[u][j];
        int temp = -inf;
        if (v.fi == par[u] && t == 0){
            temp = v.se;
        }
        else if (v.fi != par[u]){
            par[v.fi] = u;
            ans += solve(v.fi, 0);
            temp = v.se-solve(v.fi, 0)+solve(v.fi, 1);
        }

        if (temp > mx1)
            swap(mx1, mx2), mx1 = temp;
        else if (temp > mx2)
            mx2 = temp;
    }

    if (mx1 != -inf && mx2 != -inf)
        ans = max(ans, ans+mx1+mx2);
    return dp[u][t] = ans;
}
*/

void fix(int u){
    for (int j = 0; j < adj[u].size(); j++){
        ii v = adj[u][j];
        if (v.fi == par[u].fi)
            adj[u].erase(adj[u].begin()+j);
    }

    for (int j = 0; j < adj[u].size(); j++){
        ii v = adj[u][j];

        par[v.fi] = mp(u, v.se);
        fix(v.fi);
    }
}

bool comp(ii a, ii b){
    return (a.se+dp[a.fi][1]-dp[a.fi][0] > b.se+dp[b.fi][1]-dp[b.fi][0]);
}

void solve(int u){
    // t == 0 -- parent is not covered
    // t == 1 -- parent is covered

    if (adj[u].size() == 0)
        return void(dp[u][0] = dp[u][1] = 0);

    int sum = 0;
    for (auto v: adj[u])
        solve(v.fi), sum += dp[v.fi][0];
    sort(adj[u].begin(), adj[u].end(), comp);

    dp[u][0] = dp[u][1] = sum;
    if (adj[u].size() >= 1){
        ii v = adj[u][0];
        sum -= dp[v.fi][0]-dp[v.fi][1];
        dp[u][0] = max(dp[u][0], sum + v.se+par[u].se);
    }
    if (adj[u].size() >= 2){
        ii v = adj[u][1];
        sum -= dp[v.fi][0]-dp[v.fi][1];
        dp[u][0] = max(dp[u][0], sum + v.se+adj[u][0].se);
        dp[u][1] = max(dp[u][1], sum + v.se+adj[u][0].se);
    }
}

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

    fix(1);
    solve(1);

    printf("%d\n", dp[1][1]);
    return 0;
}
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/

Compilation message (stderr)

beads.cpp: In function 'void fix(int)':
beads.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
beads.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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