제출 #744554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
744554		AtinaR	Dreaming (IOI13_dreaming)	C++14	47 / 100	76 ms	8524 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(auto neighbour:graph[curr])
        {
            int newidx=neighbour.first;
            int cost=neighbour.second;
            if(vis[newidx]!=status)
            {
                vis[newidx]=status;
                q.push(newidx);
                dist[newidx]=dist[curr]+cost;
                if(max_dist<dist[newidx])
                {
                    max_dist=dist[newidx];
                    index=newidx;
                }
            }
        }
    }
    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<tmp)
            {
                ans=tmp;
            }
            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());
    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: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23