oj.uz

Submission #8861

# Submission time Handle Problem Language Result Execution time Memory
8861 2014-09-22T12:08:33 Z dohyun0324 Beads and wires (APIO14_beads) C++
13 / 100
 18 ms 9848 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]; // 부모-나-자식, 자식이 빨강
int D4[M]; // 부모-나-자식, 자식이 파랑
int dap,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 pro_D1(int x)
{
    int i,big=0,sum=0,k;
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        k=max(D1[con[x][i]],D3[con[x][i]]+len[x][i]);
        big=max(big,D2[con[x][i]]-k,D4[con[x][i]]+len[x][i]-k);
        D1[x]+=k;
    }
    D1[x]+=big;
}
void pro_D2(int x)
{
    int i;
    for(i=1;i<=4;i++) big1[i]=-214748364;
    sum=0;
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        arr[i]=max(D1[con[x][i]],D3[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]=-214748364;
    }
    else
    {
        big=-214748364;
        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;
    }
}
void pro_D3(int x)
{
    int i;
    sum=0;
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        sum+=max(D1[con[x][i]],D3[con[x][i]]+len[x][i]);
        arr[i]=max(D1[con[x][i]],D3[con[x][i]]+len[x][i]);
    }
    dap=-214748364;
    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;
    }
    D3[x]=dap+sum;
}
void pro_D4(int x)
{
    int i;
    sum=0;
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        sum+=max(D1[con[x][i]],D3[con[x][i]]+len[x][i]);
        arr[i]=max(D1[con[x][i]],D3[con[x][i]]+len[x][i]);
    }
    dap=-214748364;
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        big=len[x][i]+D2[con[x][i]]-arr[i];
        if(dap<big) dap=big;
    }
    D4[x]=dap+sum;
    if(con[x].size()==1 && x!=1) D3[x]=-214748364, D4[x]=-214748364;
}
void dfs(int x)
{
    int i,j;
    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
    pro_D1(x);
    //D2 : 자식-나-자식
    pro_D2(x);
    //D3 : 부모-나-자식, 부모가 연결X
    pro_D3(x);
    //D4 : 부모-나-자식, 부모가 연결O
    pro_D4(x);
}
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 pro_D1(int)':
beads.cpp:22:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:21:17: warning: unused variable 'sum' [-Wunused-variable]
     int i,big=0,sum=0,k;
                 ^~~
beads.cpp: In function 'void pro_D2(int)':
beads.cpp:36:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:42:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:48:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:54:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:60:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp: In function 'void pro_D3(int)':
beads.cpp:85:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:92:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp: In function 'void pro_D4(int)':
beads.cpp:104:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:111:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp: In function 'void dfs(int)':
beads.cpp:124:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:122:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j;
           ^
beads.cpp: In function 'int main()':
beads.cpp:141:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
beads.cpp:144: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 18 ms 9848 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 9 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 12 ms 9728 KB Output is correct
11 Correct 10 ms 9728 KB Output is correct
12 Correct 10 ms 9728 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 9848 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 9 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 12 ms 9728 KB Output is correct
11 Correct 10 ms 9728 KB Output is correct
12 Correct 10 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 18 ms 9848 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 9 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 12 ms 9728 KB Output is correct
11 Correct 10 ms 9728 KB Output is correct
12 Correct 10 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 18 ms 9848 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 9 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 12 ms 9728 KB Output is correct
11 Correct 10 ms 9728 KB Output is correct
12 Correct 10 ms 9728 KB Output is correct
13 Incorrect 10 ms 9728 KB Output isn't correct
14 Halted 0 ms 0 KB -