Submission #744563

#	Time	Username	Problem	Language	Result	Execution time	Memory
744563		AtinaR	Dreaming (IOI13_dreaming)	C++98	100 / 100	107 ms	10040 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int MAX=1e5+10;
const int INF=(1<<30);
vector<pair<int,int> > graph[MAX];
vector<int> radius;
int dist[MAX];
int vis[MAX];
int FindEnd(int start, int status)
{
    queue<int> q;
    int index,max_dist;
    index=start;max_dist=0;
    q.push(start);
    vis[start]=status;
    dist[start]=0;
    while(!q.empty())
    {
        int curr=q.front();
        q.pop();
        for(int i=0; i<(int)graph[curr].size(); i++)
        {
            int y=graph[curr][i].first;
            if(vis[y]!=status)
            {
                q.push(y);
                dist[y]=dist[curr]+graph[curr][i].second;
                vis[y]=status;
                if(max_dist<dist[y])
                {
                    max_dist=dist[y];
                    index=y;
                }
            }
        }
    }
    return index;

}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    int ans=0,tmp,End;
    memset(vis,0,sizeof(vis));
    memset(dist,0,sizeof(dist));
    for(int i=0; i<M; i++)
    {
        int a=A[i];
        int b=B[i];
        int cena=T[i];
        graph[a].push_back({b,cena});
        graph[b].push_back({a,cena});
    }
    for(int i=0; i<N; i++)
    {
        if(vis[i]==0)
        {
            int y=FindEnd(i,1);
            int x=FindEnd(y,2);
            tmp=End=dist[x];
            if(ans<End)
            {
                ans=End;
            }
            while(dist[x]>0)
            {
                for(int j=0; j<(int)graph[x].size(); j++)
                {
                    y=graph[x][j].first;
                    if(dist[x]==dist[y]+graph[x][j].second)
                    {
                        x=y;
                        break;
                    }
                }
                tmp=min(tmp,max(dist[x],End-dist[x]));
            }
            radius.push_back(tmp);
        }
    }
    sort(radius.begin(),radius.end());
    reverse(radius.begin(),radius.end());
    if (radius.size() == 2) ans = max(ans,radius[0]+radius[1]+L);
    else if (radius.size() > 2)
    {
        int last = max(radius[0]+radius[1],radius[1]+radius[2]+L);
        last = min(max(radius[1]+radius[0],radius[0]+radius[2]+L),last);
        last = min(max(radius[2]+radius[0],radius[0]+radius[1]+L),last);
        ans = max(ans,last+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