oj.uz

Submission #581049

# Submission time Handle Problem Language Result Execution time Memory
581049 2022-06-22T08:48:03 Z 박상훈(#8359) Beads and wires (APIO14_beads) C++17
0 / 100
 4 ms 5008 KB 
#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 (par[pa]!=-1) dp2[s][0] += dp2[pa][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 += w;
        nmx.push_back(dp[v][0]+w - dp[v][1]);
    }
    if (pa!=-1){
        ns += w0;
        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);

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

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
beads.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%d %d %d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5008 KB Output isn't correct
2 Halted 0 ms 0 KB -