제출 #235539

#제출 시각아이디문제언어결과실행 시간메모리
235539Autoratch구슬과 끈 (APIO14_beads)C++14
13 / 100
8 ms5120 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 1;

int n;
vector<pair<int,int> > adj[N];
int a[N][4];

void dfs(int u,int p)
{
    a[u][1] = -2e9;
    a[u][3] = -2e9;
    int m3 = -2e9,m21 = -2e9,m22 = -2e9,m01 = -2e9,m02 = -2e9,v2,v0;
    for(auto [d,v] : adj[u]) if(v!=p)
    {
        dfs(v,u); 
        int each = max(a[v][0],a[v][2]),ez = a[v][1]+d;
        a[u][0]+=max(each,ez);
 
        a[u][1] = max(a[u][1],a[v][0]+d-max(each,ez));
        
        m3 = max(m3,a[v][3]+d-max(each,ez));
    
        if(a[v][2]+d-max(each,ez)>m21) m22 = m21,m21 = a[v][2]+d-max(each,ez),v2 = v;
        else if(a[v][2]+d-max(each,ez)>m22) m22 = a[v][2]+d-max(each,ez);

        if(a[v][0]+d-max(each,ez)>m01) m02 = m01,m01 = a[v][0]+d-max(each,ez),v0 = v;
        else if(a[v][0]+d-max(each,ez)>m02) m02 = a[v][0]+d-max(each,ez);

        a[u][3] = max(a[u][3],a[v][2]+d-max(each,ez));
    }
    a[u][1]+=a[u][0];
    a[u][3]+=a[u][0];
    if(m01!=-2e9 and m02!=-2e9) a[u][2] = max(a[u][2],m01+m02);
    if(m01!=-2e9 and m21!=-2e9 and v2!=v0) a[u][2] = max(a[u][2],m01+m21);
    if(m02!=-2e9 and m21!=-2e9) a[u][2] = max(a[u][2],m02+m21);
    if(m01!=-2e9 and m22!=-2e9) a[u][2] = max(a[u][2],m01+m22);
    a[u][2] = max(a[u][2],m3);
    a[u][2]+=a[u][0];
    
/*
    if(u==1)
    {
        cout << m01 << ' ' << m02 << ' ' << m21 << ' ' << m22 << endl;
    }
    
    cout << u << ' ' << lft << endl;
    for(int i = 0;i < 4;i++) cout << a[u][i] << ' ';
    cout << endl;
*/
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n;
    for(int i = 0;i < n-1;i++)
    {
        int a,b,d;
        cin >> a >> b >> d;
        adj[a].push_back({d,b});
        adj[b].push_back({d,a});
    }
    dfs(1,0);
    cout << max(a[1][0],a[1][2]);
}

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

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:15:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [d,v] : adj[u]) if(v!=p)
              ^
beads.cpp:36:32: warning: 'v0' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(m01!=-2e9 and m21!=-2e9 and v2!=v0) a[u][2] = max(a[u][2],m01+m21);
        ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
beads.cpp:36:32: warning: 'v2' may be used uninitialized in this function [-Wmaybe-uninitialized]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...