oj.uz

Submission #8579

# Submission time Handle Problem Language Result Execution time Memory
8579 2014-09-17T11:59:51 Z dohyun0324 Beads and wires (APIO14_beads) C++
0 / 100
 15 ms 14464 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>con[200010];
vector<int>len[200010];
vector<int>d[200010];
int sum,x,y,c,n,D[200010],big,big1,big2,p1,p2,ch[200010],anc[200010];
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]);
    }
    big=0;
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        sum=0; big=0;
        for(j=0;j<con[con[x][i]].size();j++) sum+=d[con[x][i]][j];
        for(j=0;j<con[con[x][i]].size();j++)
        {
            if(con[con[x][i]][j]==x) continue;
            if(big<sum-d[con[x][i]][j]+D[con[con[x][i]][j]]+len[x][i]+len[con[x][i]][j])
            {
                big=sum-d[con[x][i]][j]+D[con[con[x][i]][j]]+len[x][i]+len[con[x][i]][j];
            }
        }
        d[x][i]=max(big,D[con[x][i]]);
    }
    big1=-2147483647;
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        if(big1<D[con[x][i]]+len[x][i]-d[x][i])
        {
            big1=D[con[x][i]]+len[x][i]-d[x][i];
            p1=i;
        }
    }
    big2=-2147483647;
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        if(i!=p1 && big2<D[con[x][i]]+len[x][i]-d[x][i])
        {
            big2=D[con[x][i]]+len[x][i]-d[x][i];
            p2=i;
        }
    }
    sum=0;
    for(i=0;i<con[x].size();i++)
    {
        if(anc[x]==con[x][i]) continue;
        sum+=d[x][i];
    }
    if(big1==-2147483647 || big2==-2147483647) D[x]=sum;
    else D[x]=max(sum,sum+big1+big2);
}
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);
        d[x].push_back(0); d[y].push_back(0);
    }
    dfs(1);
    printf("%d",D[1]);
    return 0;
}

Compilation message

beads.cpp: In function 'void dfs(int)':
beads.cpp:13:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:19:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<con[con[x][i]].size();j++) sum+=d[con[x][i]][j];
                 ~^~~~~~~~~~~~~~~~~~~~~~
beads.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<con[con[x][i]].size();j++)
                 ~^~~~~~~~~~~~~~~~~~~~~~
beads.cpp:35: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:55:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<con[x].size();i++)
             ~^~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
beads.cpp:69: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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 14 ms 14464 KB Output is correct
3 Correct 15 ms 14336 KB Output is correct
4 Correct 14 ms 14328 KB Output is correct
5 Correct 15 ms 14336 KB Output is correct
6 Incorrect 15 ms 14464 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 14 ms 14464 KB Output is correct
3 Correct 15 ms 14336 KB Output is correct
4 Correct 14 ms 14328 KB Output is correct
5 Correct 15 ms 14336 KB Output is correct
6 Incorrect 15 ms 14464 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 14 ms 14464 KB Output is correct
3 Correct 15 ms 14336 KB Output is correct
4 Correct 14 ms 14328 KB Output is correct
5 Correct 15 ms 14336 KB Output is correct
6 Incorrect 15 ms 14464 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 14 ms 14464 KB Output is correct
3 Correct 15 ms 14336 KB Output is correct
4 Correct 14 ms 14328 KB Output is correct
5 Correct 15 ms 14336 KB Output is correct
6 Incorrect 15 ms 14464 KB Output isn't correct
7 Halted 0 ms 0 KB -