제출 #63610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63610		MKopchev	꿈 (IOI13_dreaming)	C++14	100 / 100	139 ms	13044 KiB

dreaming

#include<bits/stdc++.h>
#include"dreaming.h"
using namespace std;
const int nmax=1e5+42;
vector< pair<int/*node*/,int/*distance*/> > adj[nmax];
bool been[nmax];
int dist[nmax];
int parent[nmax];
vector<int> active;
void dfs(int node,int par,int d)
{
    if(been[node])return;
    active.push_back(node);
    parent[node]=par;
    been[node]=1;
    dist[node]=d;
    for(auto k:adj[node])
        dfs(k.first,node,k.second+d);
}
vector<int> comp;
bool cmp(int x,int y)
{
return x>y;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for(int i=0;i<M;i++)
    {
    adj[A[i]].push_back({B[i],T[i]});
    adj[B[i]].push_back({A[i],T[i]});
    }
int O=0;
for(int i=0;i<N;i++)
    if(been[i]==0)
    {
    active={};
    dfs(i,0,0);
    int where=i;
    for(auto k:active)
        if(dist[where]<dist[k])where=k;

    for(auto k:active)
        {
        been[k]=0;
        dist[k]=0;
        }

    active={};
    dfs(where,0,0);
    int other=where;
    for(auto k:active)
        if(dist[other]<dist[k])other=k;
    /*
    cout<<i<<" -> "<<where<<" "<<other<<" "<<dist[other]<<endl;
    cout<<"active: ";for(auto k:active)cout<<k<<" ";cout<<endl;
    cout<<"parent: ";for(int i=1;i<=N;i++)cout<<parent[i]<<" ";cout<<endl;
    */
    int ans=dist[other],f=0,total=dist[other];
    O=max(O,ans);
    int run=other;
        while(other!=where)
        {
        for(auto k:adj[other])
            if(k.first==parent[other])f=f+k.second;
        other=parent[other];
        if(max(f,total-f)<ans)run=other;
        ans=min(ans,max(f,total-f));
        }
    //cout<<i<<" -> "<<ans<<" "<<run<<endl;
    for(auto k:active)
        been[k]=0;
    active={};
    dfs(run,0,0);
    //for(auto k:active)cout<<k<<" -> "<<dist[k]<<endl;
    for(auto k:active)
        assert(dist[k]<=ans);
    comp.push_back(ans);
    //cout<<i<<" -> "<<ans<<endl;
    }
sort(comp.begin(),comp.end(),cmp);
if(comp.size()==1)return max(O,comp[0]);
if(comp.size()==2)return max(comp[0]+L+comp[1],O);
return max(O,max(comp[0]+L+comp[1],comp[1]+L+L+comp[2]));
}
/*
const int N=12,M=8,L=2;
int a[M]={0, 8, 2, 5, 5, 1, 1, 10};
int b[M]={8, 2, 7, 11, 1, 3, 9, 6};
int t[M]={4, 2, 4, 3, 7, 1, 5, 3};
int main()
{
cout<<travelTime(N,M,L,a,b,t)<<endl;
}
*/

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