oj.uz

답안 #235531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
235531 2020-05-28T12:41:27 Z Autoratch 구슬과 끈 (APIO14_beads) C++14
0 / 100
 8 ms 5120 KB 
#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] = INT_MIN;
    a[u][3] = INT_MIN;
    int m3 = INT_MIN,m21 = INT_MIN,m22 = INT_MIN,m01 = INT_MIN,m02 = INT_MIN,v2,v0;
    int ed = 0,lft = 0;
    for(auto [d,v] : adj[u]) if(v!=p)
    {
        dfs(v,u); 
        int each = max(a[v][0],a[v][2]);
        lft+=each;
        if(a[v][1]!=INT_MIN) a[u][0]+=a[v][1]+d-each;
        
        if(a[v][1]==INT_MIN) a[u][1] = max(a[u][1],a[v][0]+d-each);
        else a[u][1] = max(a[u][1],a[v][0]-a[v][1]);
        
        if(a[v][3]!=INT_MIN)
        {
            if(a[v][1]==INT_MIN) m3 = max(m3,a[v][3]+d-each);
            else m3 = max(m3,a[v][3]-a[v][1]);
        }

        if(a[v][1]==INT_MIN)
        {
            if(a[v][2]+d-each>m21) m22 = m21,m21 = a[v][2]+d-each,v2 = v;
            else if(a[v][2]+d-each>m22) m22 = a[v][2]+d-each;
        }
        else
        {
            if(a[v][2]-a[v][1]>m21) m22 = m21,m21 = a[v][2]-a[v][1],v2 = v;
            else if(a[v][2]-a[v][1]>m22) m22 = a[v][2]-a[v][1];
        }

        if(a[v][1]==INT_MIN)
        {
            if(a[v][0]+d-each>m01) m02 = m01,m01 = a[v][0]+d-each,v0 = v;
            else if(a[v][0]+d-each>m02) m02 = a[v][0]+d-each;
        }
        else
        {
            if(a[v][0]-a[v][1]>m01) m02 = m01,m01 = a[v][0]-a[v][1],v0 = v;
            else if(a[v][0]-a[v][1]>m02) m02 = a[v][0]-a[v][1];
        }

        if(a[v][1]==INT_MIN) a[u][3] = max(a[u][3],a[v][2]+d-each);
        else a[u][3] = max(a[u][3],a[v][2]-a[v][1]);
/*
        if(u==1)
        {
            cout << a[v][0] << ' ' << a[v][1] << ' ' << a[v][2] << ' ' << d << ' ' << each << endl;
            cout << v0 << ' ' << m01 << endl;
            cout << v2 << ' ' << m21 << endl;
        }
        */
    }
    a[u][0]+=lft;
    if(a[u][1]!=INT_MIN) a[u][1]+=a[u][0];
    if(a[u][3]!=INT_MIN) a[u][3]+=a[u][0];
    if(m01!=INT_MIN and m02!=INT_MIN) a[u][2] = max(a[u][2],a[u][0]+m01+m02);
    if(m01!=INT_MIN and m21!=INT_MIN and v2!=v0) a[u][2] = max(a[u][2],a[u][0]+m01+m21);
    if(m02!=INT_MIN and m21!=INT_MIN) a[u][2] = max(a[u][2],a[u][0]+m02+m21);
    if(m01!=INT_MIN and m22!=INT_MIN) a[u][2] = max(a[u][2],a[u][0]+m01+m22);
    if(m3!=INT_MIN) a[u][2] = max(a[u][2],m3+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]);
}

Compilation message

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:16: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:15:9: warning: unused variable 'ed' [-Wunused-variable]
     int ed = 0,lft = 0;
         ^~
beads.cpp:14:81: warning: 'v0' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int m3 = INT_MIN,m21 = INT_MIN,m22 = INT_MIN,m01 = INT_MIN,m02 = INT_MIN,v2,v0;
                                                                                 ^~
beads.cpp:14:78: warning: 'v2' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int m3 = INT_MIN,m21 = INT_MIN,m22 = INT_MIN,m01 = INT_MIN,m02 = INT_MIN,v2,v0;
                                                                              ^~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Incorrect 7 ms 4992 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Incorrect 7 ms 4992 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Incorrect 7 ms 4992 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Incorrect 7 ms 4992 KB Output isn't correct
8 Halted 0 ms 0 KB -