제출 #992571

#제출 시각아이디문제언어결과실행 시간메모리
992571starBeads and wires (APIO14_beads)C++17
100 / 100
80 ms26084 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define starburst ios::sync_with_stdio(0), cin.tie(0)
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(),x.end()
#define inf 0x3f3f3f3f
#define N 200005
int n, a, b, c, ans=0;
vector<pii> adj[N];
int in[N], ex[N];
int pw[N];
void dfs(int v, int parent){
    int sum=0;//, pw=-inf;
    for (int i=0;i<adj[v].size();i++){
        int u=adj[v][i].F;
        if (u==parent){
            pw[v]=adj[v][i].S;
            swap(adj[v][i],adj[v].back());
            adj[v].pop_back();
            i--;
            continue;
        }
        dfs(u,v);
        sum+=in[u];
    }
    in[v]=ex[v]=sum;
    for (auto it:adj[v]){
        int u=it.F;
        if (u==parent) continue;
        in[v]=max(in[v], sum-in[u]+ex[u]+pw[v]+it.S);
    }
}
void dfs2(int v, int parent, int to){
    int sum=parent;
    int mx=to-parent+pw[v];
    int mxx=-inf;
    for (auto it:adj[v]){
        int u=it.F;
        if (u==parent) continue;
        sum+=in[u];
        int now=ex[u]-in[u]+it.S;
        if (mx<now){
            mxx=mx;
            mx=now;
        }
        else if (mxx<now) mxx=now;
    }
    ans=max(ans, sum);
    for (auto it:adj[v]){
        int u=it.F;
        if (u==parent) continue;
        int now=mx;
        if (now==ex[u]-in[u]+it.S) now=mxx;
        dfs2(u, max(sum-in[u], now+sum-in[u]+it.S), sum-in[u]);
    }
}
signed main(){
    starburst;
    cin >> n;
    for (int i=0;i<n-1;i++){
        cin >> a >> b >> c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }
//    for (int v=1;v<=n;v++){
////        memset(x,0,sizeof(in));
////        memset(y,0,sizeof(ex));
//        for (int i=1;i<=n;i++) in[i]=ex[i]=0;
//        dfs(v,0);
//        //dfs(v);
//        ans=max(ans, in[v]);
//    }
    pw[1]=-inf;
    dfs(1,0);
    dfs2(1,0,0);
    cout << ans;
    return 0;
}

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

beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:19:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i=0;i<adj[v].size();i++){
      |                  ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...