제출 #758635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
758635		Username4132	구슬과 끈 (APIO14_beads)	C++14	0 / 100	2 ms	4948 KiB

beads

#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)(rng);
    dfs(rn, rn, -INF);
    printf("%d\n", dp[3][rn]);
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43