Submission #922271

#	Time	Username	Problem	Language	Result	Execution time	Memory
922271		Aiperiii	Dreaming (IOI13_dreaming)	C++14	100 / 100	92 ms	17724 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int NN=1e5+5;
int l[NN],d[NN],p[NN];
vector <int> gr[NN];
vector <pair <int,int> >g[NN];
int find_set(int v){
   if(l[v]==v)return v;
   return l[v]=find_set(l[v]);
}
void union_set(int u,int v){
   u=find_set(u);
   v=find_set(v);
   if(u!=v){
     if(gr[v].size()<gr[u].size())swap(u,v);
     l[u]=v;
     for(auto x : gr[u])gr[v].pb(x);
     gr[u].clear();
   }
}
void bfs(int v){
   queue <int> q;
   q.push(v);
   while(!q.empty()){
      int v=q.front();
      q.pop();
      for(auto to : g[v]){
         if(d[to.ff]==-1){
            p[to.ff]=v;
            d[to.ff]=d[v]+to.ss;
            q.push(to.ff);
         }
      }
   }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
   for(int i=0;i<N;i++){
      l[i]=i;
      gr[i].pb(i);
   }
   for(int i=0;i<M;i++){
      union_set(A[i],B[i]);
      g[A[i]].pb({B[i],T[i]});
      g[B[i]].pb({A[i],T[i]});
   }
   vector <int> len;
   int ans=0;
   for(int i=0;i<N;i++)d[i]=-1;
   for(int i=0;i<N;i++){
      if(gr[i].size()!=0){
         d[gr[i][0]]=0;
         bfs(gr[i][0]);
         int mx=0,node=gr[i][0];
         for(auto x : gr[i]){
            if(d[x]>mx){
               mx=d[x];
               node=x;
            }
            d[x]=-1;
            p[x]=0;
         }
         d[node]=0;
         bfs(node);
         mx=0;
         int s=node;
         for(auto x : gr[i]){
            if(d[x]>mx){
               mx=d[x];
               node=x;
            }
         }
         ans=max(ans,mx);
         vector <int> path;
         path.pb(node);
         while(node!=s){
            node=p[node];
            path.pb(node);
         }
         int mn=1e9+5;
         for(auto x : path){
            mn=min(max(mx-d[x],d[x]),mn);
         }
         len.pb(mn);
         for(auto x : gr[i]){
            d[x]=-1;
            p[x]=0;
         }
      }
   }
   sort(all(len));
   for(auto x : len)ans=max(ans,x);
   if(len.size()>=2)ans=max(ans,L+len[len.size()-1]+len[len.size()-2]);
   if(len.size()>=3)ans=max(ans,2*L+len[len.size()-2]+len[len.size()-3]);
   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