Submission #7519

#	Time	Username	Problem	Language	Result	Execution time	Memory
7519		baneling100	Dreaming (IOI13_dreaming)	C++98	100 / 100	96 ms	9464 KiB

dreaming

#include "dreaming.h"
#include <algorithm>
#include <vector>
#include <queue>
#define INF 0x7fffffff

using namespace std;

typedef pair <int,int> ppair;
vector <ppair> Road[100001];
vector <int> Diameter;
vector <int> Depth;
queue <int> Q;
int Check[100001], D[100001], Path[100001][2], Ans=-1;

int MAX(int X, int Y)
{
    if(X>Y)
        return X;
    return Y;
}

void BFS(int S)
{
    int Now, Dist, i, j, Max=-1, V, Min=INF;

    Check[S]=1;
    Q.push(S);
    Q.push(0);
    while(!Q.empty())
    {
        Now=Q.front();
        Q.pop();
        Dist=Q.front();
        Q.pop();
        if(Max<Dist)
        {
            Max=Dist;
            V=Now;
        }
        j=Road[Now].size();
        for(i=0 ; i<j ; i++)
            if(!Check[Road[Now][i].first])
            {
                Check[Road[Now][i].first]=1;
                Q.push(Road[Now][i].first);
                Q.push(Dist+Road[Now][i].second);
            }
    }
    Check[V]=2;
    D[V]=0;
    Path[V][0]=-1;
    Max=-1;
    Q.push(V);
    while(!Q.empty())
    {
        Now=Q.front();
        Q.pop();
        if(Max<D[Now])
        {
            Max=D[Now];
            V=Now;
        }
        j=Road[Now].size();
        for(i=0 ; i<j ; i++)
            if(Check[Road[Now][i].first]==1)
            {
                Check[Road[Now][i].first]=2;
                D[Road[Now][i].first]=D[Now]+Road[Now][i].second;
                Path[Road[Now][i].first][0]=Now;
                Path[Road[Now][i].first][1]=Road[Now][i].second;
                Q.push(Road[Now][i].first);
            }
    }
    Diameter.push_back(Max);
    Dist=0;
    while(V>=0)
    {
        if(Min>MAX(Max,Dist))
            Min=MAX(Max,Dist);
        Dist+=Path[V][1];
        Max-=Path[V][1];
        V=Path[V][0];
    }
    Depth.push_back(Min);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    int i, j;

    for(i=0 ; i<M ; i++)
    {
        Road[A[i]].push_back(make_pair(B[i],T[i]));
        Road[B[i]].push_back(make_pair(A[i],T[i]));
    }
    for(i=0 ; i<N ; i++)
        if(!Check[i])
            BFS(i);
    j=Diameter.size();
    for(i=0 ; i<j ; i++)
    {
        if(Ans<Diameter[i])
            Ans=Diameter[i];
    }
    if(j==1)
        return Ans;
    sort(Depth.begin(),Depth.end());
    for(i=0 ; i<j-1 ; i++)
    {
        if(Ans<Depth[i]+Depth[j-1]+L)
            Ans=Depth[i]+Depth[j-1]+L;
    }
    if(j==2)
        return Ans;
    for(i=0 ; i<j-2 ; i++)
        if(Ans<Depth[i]+Depth[j-2]+2*L)
            Ans=Depth[i]+Depth[j-2]+2*L;
    return Ans;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23