Submission #581206

#	Time	Username	Problem	Language	Result	Execution time	Memory
581206		qwerasdfzxcl	Beads and wires (APIO14_beads)	C++14	100 / 100	254 ms	24988 KiB

beads

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<pair<int, int>> adj[200200];
int dp[200200][2], dp2[200200][2], par[200200], paw[200200];

void dfs(int s, int pa = -1, int w0 = 0){
    int tmp = -1e9;
    dp[s][0] = 0;
    par[s] = pa;
    paw[s] = w0;
    for (auto &[v, w]:adj[s]) if (v!=pa){
        dfs(v, s, w);
        tmp = max(tmp, dp[v][0] + w - dp[v][1]);
        dp[s][0] += dp[v][1];
    }

    if (w0+tmp>0) dp[s][1] = dp[s][0] + w0 + tmp;
    else dp[s][1] = dp[s][0];
    //if (C.size()>=2) dp[s][0] = max(dp[s][0], dp[s][0] + C[0] + C[1]);

    //printf("%d: %d %d\n", s, dp[s][0], dp[s][1]);
}

void dfs2(int s, int pa  = -1, int w0 = 0, int sum = 0, int mx = 0){
    if (pa!=-1){
        dp2[s][0] = sum - dp[s][1];

        if (w0 + mx>0) dp2[s][1] = dp2[s][0] + w0 + mx;
        else dp2[s][1] = dp2[s][0];
    }

    int ns = 0;
    vector<int> nmx = {-1000000000, -1000000000};
    for (auto &[v, w]:adj[s]) if (v!=pa){
        ns += dp[v][1];
        nmx.push_back(dp[v][0]+w - dp[v][1]);
    }
    if (pa!=-1){
        ns += dp2[s][1];
        nmx.push_back(dp2[s][0]+w0 - dp2[s][1]);
    }

    sort(nmx.begin(), nmx.end(), greater<int>());

    for (auto &[v, w]:adj[s]) if (v!=pa){
        if (nmx[0]!=dp[v][0]+w-dp[v][1]) dfs2(v, s, w, ns, nmx[0]);
        else dfs2(v, s, w, ns, nmx[1]);
    }
}

int calc(int s){
    int ret1 = 0, ret2 = 0;
    for (auto &[v, w]:adj[s]) if (v!=par[s]){
        ret1 += dp[v][1];
    }
    if (par[s]!=-1) ret1 += dp2[s][1];

    if (adj[s].size()<2) return ret1;

    vector<int> V;
    for (auto &[v, w]:adj[s]) if (v!=par[s]) V.push_back(dp[v][0]+w - dp[v][1]);
    if (par[s]!=-1) V.push_back(dp2[s][0]+paw[s] - dp2[s][1]);
    sort(V.begin(), V.end(), greater<int>());

    ret2 = ret1 + V[0] + V[1];
    return max(ret1, ret2);
}

int main(){
    int n;
    scanf("%d", &n);
    for (int i=0;i<n-1;i++){
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        adj[x].emplace_back(y, z);
        adj[y].emplace_back(x, z);
    }

    dfs(1);
    dfs2(1);

    //for (int i=1;i<=n;i++) printf("%d: %d %d\n", i, dp[i][0], dp[i][1]);
    //for (int i=1;i<=n;i++) printf("%d: %d %d\n", i, dp2[i][0], dp2[i][1]);


    int ans = 0;
    for (int i=1;i<=n;i++) ans = max(ans, calc(i));
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:13:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   13 |     for (auto &[v, w]:adj[s]) if (v!=pa){
      |                ^
beads.cpp: In function 'void dfs2(int, int, int, int, int)':
beads.cpp:36:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     for (auto &[v, w]:adj[s]) if (v!=pa){
      |                ^
beads.cpp:47:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for (auto &[v, w]:adj[s]) if (v!=pa){
      |                ^
beads.cpp: In function 'int calc(int)':
beads.cpp:55:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for (auto &[v, w]:adj[s]) if (v!=par[s]){
      |                ^
beads.cpp:63:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |     for (auto &[v, w]:adj[s]) if (v!=par[s]) V.push_back(dp[v][0]+w - dp[v][1]);
      |                ^
beads.cpp: In function 'int main()':
beads.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
beads.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d %d %d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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