oj.uz

Submission #758636

# Submission time Handle Problem Language Result Execution time Memory
758636 2023-06-15T02:59:14 Z Username4132 Beads and wires (APIO14_beads) C++14
0 / 100
 3 ms 4948 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<random>
#include<chrono>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

const int MAXN=200010, INF=2000000010;
int n, rn, dp[4][MAXN];
vector<pii> g[MAXN];
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void dfs(int v, int p, int cost){
    int sz = g[v].size() - (v!=rn), cnt=0;
    vector<pii> d1(sz), d2(sz), d3(sz);
    for(pii to:g[v]) if(to.F!=p){
        dfs(to.F, v, to.S);
        dp[1][v]+=dp[0][to.F];
        d1[cnt]={to.S+dp[1][to.F]-dp[0][to.F], cnt};
        d2[cnt]={to.S+dp[2][to.F]-dp[0][to.F], cnt};
        d3[cnt]={dp[3][to.F]-dp[0][to.F], cnt};
        cnt++;
    }
    sort(d1.begin(), d1.end(), greater<pii>());
    sort(d2.begin(), d2.end(), greater<pii>());
    sort(d3.begin(), d3.end(), greater<pii>());

    dp[0][v]=(sz==0? 0 : max(d1[0].F + cost, 0))+dp[1][v];
    dp[2][v]=dp[1][v];
    if(sz>1){
        int mx;
        if(d1[0].S!=d2[0].S) mx=d1[0].F+d2[0].F;
        else mx=max(d1[0].F+d2[1].F, d1[1].F+d2[0].F);
        if(mx>0) dp[2][v]=mx+dp[1][v];
    }
    if(sz>0) dp[2][v]=max(dp[2][v], dp[1][v]+d3[0].F);
    if(sz>1){
        int mx;
        if(d1[0].S!=d3[0].S) mx=d1[0].F+d3[0].F;
        else mx=max(d1[0].F+d3[1].F, d1[1].F+d3[0].F);
        dp[3][v]=mx+dp[1][v]+cost;
    }
    if(sz>0) dp[3][v]=max(dp[3][v], dp[1][v]+d2[0].F+cost);
    dp[3][v]=max(dp[3][v], dp[2][v]);
    dp[3][v]=max(dp[3][v], dp[0][v]);
}

int main(){
    scanf("%d", &n);
    forn(i, n-1){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c); --a, --b;
        g[a].PB({b, c}), g[b].PB({a, c});
    }
    rn = uniform_int_distribution<int>(0, n-1)(rng);
    dfs(rn, rn, -INF);
    printf("%d\n", dp[3][rn]);
}

Compilation message

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

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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