oj.uz

Submission #18623

# Submission time Handle Problem Language Result Execution time Memory
18623 2016-02-12T16:58:28 Z ggoh Dreaming (IOI13_dreaming) C++
0 / 100
 70 ms 12348 KB 
#include "dreaming.h"
#include<cstdio>
#include<vector>
#include<algorithm>
struct AA{
    int to,cost;
};
std::vector<AA>G[100002];
int ans,i,m,t,st[100002],back[100002],backlen[100002],pos,len,K,v[100002],vv[100002];
void dfs(int x,int l)
{
    for(int j=0;j<G[x].size();j++)
    {
        AA u=G[x][j];
        if(!v[u.to])
        {
            if(m<=l+u.cost)
            {
                pos=u.to;m=l+u.cost;
            }
            v[u.to]=1;
            dfs(u.to,l+u.cost);
        }
    }
}
void dfs2(int x,int l)
{
    for(int j=0;j<G[x].size();j++)
    {
        AA u=G[x][j];
        if(!vv[u.to])
        {
            if(m<=l+u.cost)
            {
                pos=u.to;m=l+u.cost;
            }
            vv[u.to]=1;
            back[u.to]=x;
            backlen[u.to]=u.cost;
            dfs2(u.to,l+u.cost);
        }
    }
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
    for(i=0;i<M;i++)
    {
        G[A[i]+1].push_back({B[i]+1,T[i]});
        G[B[i]+1].push_back({A[i]+1,T[i]});
    }
    for(i=1;i<=N;i++)
    {
        if(!v[i])
        {
            v[i]=1;
            m=0;
            pos=i;
            dfs(i,0);
            m=0;
            back[pos]=-1;
            vv[pos]=1;
            dfs2(pos,0);
            len=std::max(len,m);
            K=0;st[t]=m;
            while(back[pos]!=-1)
            {
                K+=backlen[pos];
                st[t]=std::min(st[t],std::max(K,m-K));
                pos=back[pos];
            }
            t++;
        }
    }
    std::sort(st,st+t);
    if(t==1)return len;
    else if(t==2)ans=std::max(st[t-1]+st[t-2]+L,len);
    else
    {
        int m1=st[t-1],m2=st[t-2],m3=st[t-3];
        ans=std::max(len,m1+L+m2);
        ans=std::max(ans,m2+2*L+m3);
    }
}

Compilation message

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:12:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<G[x].size();j++)
                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:28:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<G[x].size();j++)
                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 12348 KB Output is correct
2 Correct 70 ms 12280 KB Output is correct
3 Correct 41 ms 8952 KB Output is correct
4 Correct 11 ms 4096 KB Output is correct
5 Correct 16 ms 3456 KB Output is correct
6 Correct 17 ms 4736 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 12348 KB Output is correct
2 Correct 70 ms 12280 KB Output is correct
3 Correct 41 ms 8952 KB Output is correct
4 Correct 11 ms 4096 KB Output is correct
5 Correct 16 ms 3456 KB Output is correct
6 Correct 17 ms 4736 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 12348 KB Output is correct
2 Correct 70 ms 12280 KB Output is correct
3 Correct 41 ms 8952 KB Output is correct
4 Correct 11 ms 4096 KB Output is correct
5 Correct 16 ms 3456 KB Output is correct
6 Correct 17 ms 4736 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 6764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 12348 KB Output is correct
2 Correct 70 ms 12280 KB Output is correct
3 Correct 41 ms 8952 KB Output is correct
4 Correct 11 ms 4096 KB Output is correct
5 Correct 16 ms 3456 KB Output is correct
6 Correct 17 ms 4736 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 12348 KB Output is correct
2 Correct 70 ms 12280 KB Output is correct
3 Correct 41 ms 8952 KB Output is correct
4 Correct 11 ms 4096 KB Output is correct
5 Correct 16 ms 3456 KB Output is correct
6 Correct 17 ms 4736 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -