Submission #208003

#	Time	Username	Problem	Language	Result	Execution time	Memory
208003		Andrei_Cotor	Dreaming (IOI13_dreaming)	C++11	100 / 100	108 ms	17148 KiB

dreaming

#include<dreaming.h>
#include<vector>
#include<algorithm>

using namespace std;

vector<pair<int,int> > V[100005];
int DistMax[100005],Dist[100005],R[100005],Viz[100005];

int dfs(int nod, int cc)
{
    Viz[nod]=cc;
    int mx1=0,mx2=0;
    int rez=0;

    for(auto other:V[nod])
    {
        if(Viz[other.first])
            continue;

        rez=max(rez,dfs(other.first,cc));

        int val=DistMax[other.first]+other.second;
        if(val>=mx1)
        {
            mx2=mx1;
            mx1=val;
        }
        else if(val>mx2)
            mx2=val;
    }

    DistMax[nod]=mx1;
    rez=max(rez,mx1+mx2);
    return rez;
}

int distmin(int nod, int p, int dist)
{
    int rez=max(dist,DistMax[nod]);

    int mx1=0,mx2=0;
    for(auto other:V[nod])
    {
        if(other.first==p)
            continue;

        int val=DistMax[other.first]+other.second;
        if(val>=mx1)
        {
            mx2=mx1;
            mx1=val;
        }
        else if(val>mx2)
            mx2=val;
    }

    for(auto other:V[nod])
    {
        if(other.first==p)
            continue;

        int val=DistMax[other.first]+other.second;
        if(val!=mx1)
            rez=min(rez,distmin(other.first,nod,max(mx1,dist)+other.second));
        else
            rez=min(rez,distmin(other.first,nod,max(mx2,dist)+other.second));
    }
    return rez;
}

int travelTime(int n, int M, int L, int A[], int B[], int T[])
{
    for(int i=0; i<M; i++)
    {
        V[A[i]+1].push_back({B[i]+1,T[i]});
        V[B[i]+1].push_back({A[i]+1,T[i]});
    }

    int nrc=0;
    int rez=0;
    for(int i=1; i<=n; i++)
    {
        if(!Viz[i])
        {
            nrc++;
            rez=max(rez,dfs(i,nrc));
            R[nrc]=i;
        }
    }

    for(int i=1; i<=nrc; i++)
        Dist[i]=distmin(R[i],0,0);

    sort(Dist+1,Dist+nrc+1);

    if(nrc>=2)
        rez=max(rez,Dist[nrc]+Dist[nrc-1]+L);
    if(nrc>=3)
        rez=max(rez,Dist[nrc-1]+Dist[nrc-2]+2*L);

    return rez;
}

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