oj.uz

Submission #8833

# Submission time Handle Problem Language Result Execution time Memory
8833 2014-09-20T14:44:48 Z dohyun0324 Beads and wires (APIO14_beads) C++
13 / 100
 10 ms 9728 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
#define M 200010
using namespace std;
vector<int>con[M];
vector<int>len[M];
int D1[M]; // 아무것도 연결 X
int D2[M]; // 자식-나-자식
int D3[M]; // 부모-나-자식, 부모가 연결 X
int D4[M]; // 부모-나-자식, 부모가 연결 O
int p,w,sum,x,y,c,n,big,big1[5],p1,p2,p3,p4,ch[200010],anc[200010],arr[200010];
int max(int x,int y,int z)
{
    if(x>=y && x>=z) return x;
    if(y>=x && y>=z) return y;
    return z;
}
void dfs(int x)
{
    int i,j,dap;
    ch[x]=1;
    for(i=0;i<con[x].size();i++)
    {
        if(ch[con[x][i]]==1){anc[x]=con[x][i]; continue;}
        dfs(con[x][i]);
    }
    //D1 : 아무것도 연결 X
    for(i=0;i<con[x].size();i++)
    {
        big=0;
        if(anc[x]==con[x][i]) continue;
        big=max(D1[con[x][i]],D2[con[x][i]],D3[con[x][i]]+len[x][i]);
        D1[x]+=big;
    }
    //D2 : 자식-나-자식
    for(i=1;i<=4;i++) big1[i]=-2147483647;
    sum=0;
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        arr[i]=max(D1[con[x][i]],D2[con[x][i]],D4[con[x][i]]+len[x][i]);
        sum+=arr[i];
    }
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        w=big1[1]; big1[1]=max(big1[1],len[x][i]+D1[con[x][i]]-arr[i]);
        if(w!=big1[1]) p1=i;
    }
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i] || p1==i) continue;
        w=big1[2]; big1[2]=max(big1[2],len[x][i]+D1[con[x][i]]-arr[i]);
        if(w!=big1[2]) p2=i;
    }
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        w=big1[3]; big1[3]=max(big1[3],len[x][i]+D2[con[x][i]]-arr[i]);
        if(w!=big1[3]) p3=i;
    }
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i] || p3==i) continue;
        w=big1[4]; big1[4]=max(big1[4],len[x][i]+D2[con[x][i]]-arr[i]);
        if(w!=big1[4]) p4=i;
    }
    if((x==1 && con[x].size()<=1) || (x!=1 && con[x].size()<=2)) D2[x]=sum;
    else
    {
        big=-2147483647;
        if(big<big1[1]+big1[2]) big=big1[1]+big1[2];
        if(p1!=p3 && big<big1[1]+big1[3]) big=big1[1]+big1[3];
        if(p1!=p4 && big<big1[1]+big1[4]) big=big1[1]+big1[4];
        if(p2!=p3 && big<big1[2]+big1[3]) big=big1[2]+big1[3];
        if(p2!=p4 && big<big1[2]+big1[4]) big=big1[2]+big1[4];
        D2[x]=sum+big;
    }
    //D3 : 부모-나-자식, 부모가 연결X
    sum=0;
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        sum+=max(D1[con[x][i]],D2[con[x][i]],D4[con[x][i]]+len[x][i]);
        arr[i]=max(D1[con[x][i]],D2[con[x][i]],D4[con[x][i]]+len[x][i]);
    }
    dap=-2147483647;
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        big=len[x][i]+max(D1[con[x][i]],D2[con[x][i]])-arr[i];
        if(dap<big) dap=big;
    }
    D3[x]=dap+sum;
    //D4 : 부모-나-자식, 부모가 연결O
    sum=0;
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        sum+=max(D1[con[x][i]],D2[con[x][i]],D4[con[x][i]]+len[x][i]);
        arr[i]=max(D1[con[x][i]],D2[con[x][i]],D4[con[x][i]]+len[x][i]);
    }
    dap=-2147483647;
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        big=len[x][i]+D1[con[x][i]]-arr[i];
        if(dap<big) dap=big;
    }
    D4[x]=dap+sum;
    if(con[x].size()==1 && x!=1) D3[x]=-2147483647, D4[x]=-2147483647;
}
int main()
{
    int i;
    scanf("%d",&n);
    for(i=1;i<n;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        con[x].push_back(y); con[y].push_back(x);
        len[x].push_back(c); len[y].push_back(c);
    }
    dfs(1);
    printf("%d",max(D1[1],D2[1]));
    return 0;
}

Compilation message

beads.cpp: In function 'void dfs(int)':
beads.cpp:23:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:29:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:39:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:45:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:51:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:57:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:63:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:82:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:89:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:98:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:105:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:21:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j,dap;
           ^
beads.cpp: In function 'int main()':
beads.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
beads.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&x,&y,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 9 ms 9728 KB Output is correct
5 Correct 10 ms 9700 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 10 ms 9728 KB Output is correct
11 Correct 10 ms 9728 KB Output is correct
12 Correct 9 ms 9728 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 9 ms 9728 KB Output is correct
5 Correct 10 ms 9700 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 10 ms 9728 KB Output is correct
11 Correct 10 ms 9728 KB Output is correct
12 Correct 9 ms 9728 KB Output is correct
13 Incorrect 10 ms 9728 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 9 ms 9728 KB Output is correct
5 Correct 10 ms 9700 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 10 ms 9728 KB Output is correct
11 Correct 10 ms 9728 KB Output is correct
12 Correct 9 ms 9728 KB Output is correct
13 Incorrect 10 ms 9728 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 9 ms 9728 KB Output is correct
5 Correct 10 ms 9700 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 10 ms 9728 KB Output is correct
11 Correct 10 ms 9728 KB Output is correct
12 Correct 9 ms 9728 KB Output is correct
13 Incorrect 10 ms 9728 KB Output isn't correct
14 Halted 0 ms 0 KB -