Submission #922273

#	Time	Username	Problem	Language	Result	Execution time	Memory
922273		Aiperiii	Dreaming (IOI13_dreaming)	C++14	100 / 100	58 ms	11224 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 <pair <int,int> >g[NN];
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<M;i++){
      g[A[i]].pb({B[i],T[i]});
      g[B[i]].pb({A[i],T[i]});
   }
   
   queue <int> q;
   int cnt=-1;
   vector <int> grt(N,-1);
   for(int i=0;i<N;i++){
      if(grt[i]==-1){
         q.push(i);
         cnt++;
         grt[i]=cnt;
         while(!q.empty()){
            int v=q.front();
            q.pop();
            for(auto to : g[v]){
               if(grt[to.ff]==-1){
                  grt[to.ff]=grt[v];
                  q.push(to.ff);
               }
            }
         }
      }
   }
   vector <vector <int> > gr(cnt+1);
   for(int i=0;i<N;i++){
      gr[grt[i]].pb(i);
   }
   vector <int> len;
   int ans=0;
   for(int i=0;i<N;i++)d[i]=-1;
   for(int i=0;i<gr.size();i++){
      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;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for(int i=0;i<gr.size();i++){
      |                ~^~~~~~~~~~

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