Submission #1312682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312682		kevin264	Dreaming (IOI13_dreaming)	C++20	100 / 100	258 ms	35288 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define sz(x) (int)(x.size()) 
#define ff first
#define ss second
#define m_p make_pair
#define INF INT_MAX
#define OO LLONG_MAX
using vi=vector<int>;
using vvi=vector<vi>; 
using pii=pair<int,int>; 
using vvpii = vector<vector<pii > >;
using u_m=unordered_map<int,int>;
template<typename T> using inverse_pq = priority_queue<T,vector<T>, greater<T> >; 
template<typename T=int> void cin_vector(vector<T> &v) {for(int& i : v) cin>>i;}

pair<int,u_m> djikstra(int start, unordered_map<int, vector<pii> >& g){
inverse_pq<pii> pq;
u_m dist; 
pii ans={-1,-1};
pq.push({0,start});
dist[start]=0; 
while(!pq.empty()){
   int w=pq.top().ff,top=pq.top().ss; pq.pop();
   if(w>dist[top]) continue;  
   if(ans.ss<w) ans={top,w};   
   for(auto i :g[top]){
    int d=i.ss+w;
    if(dist.find(i.ff)==dist.end() or dist[i.ff]>d){
        dist[i.ff]=d;
        pq.push({d,i.ff});
    }
   }
}
return m_p(ans.ff,dist);
}

pii get_diameter_radius(unordered_map<int, vector<pii> >& g){
pair<int,u_m> pr=djikstra(g.begin()->ff,g);
int a=pr.ff;
pr=djikstra(a,g);
u_m dista=pr.ss;
u_m distb=djikstra(pr.ff,g).ss;
int radius=-1;
for(auto number : g){
   // cout<<i<<": "<<dista[i]<<" "<<distb[i]<<' '<<max(dista[i],distb[i])<<endl;
   int i=number.ff;
radius=radius==-1 or max(dista[i],distb[i])<radius ? max(dista[i],distb[i]) : radius;
}

return {distb[a],radius};
}

int travelTime(int N, int M, int L, 
  int A[], int B[], int T[]){
  int n=N;
  vector<vector<pii> > g(n); 
  for(int i=0;i<M;i++){
    g[A[i]].push_back({B[i],T[i]});
    g[B[i]].push_back({A[i],T[i]});
  }
vi p;
int maximum_diameter=0;
vector<bool> visited(n, false); 
for(int i=0;i<n;i++){
   if(!visited[i]){
    unordered_map<int,vector<pii>> current; 
    visited[i]=true;
    queue<int> q;
    q.push(i); 
    current[i]={}; 
    while(!q.empty()){
      int top=q.front(); q.pop(); 
      for(auto j : g[top]){
        if(!visited[j.ff]){
          q.push(j.ff);
          visited[j.ff]=true;
          current[j.ff].push_back({top,j.ss});
          current[top].push_back({j.ff,j.ss});
        }
      }
    }
    pii pr=get_diameter_radius(current); 
    p.push_back(pr.ss);
    maximum_diameter=max(maximum_diameter,pr.ff); 
   }
}
sort(p.begin(),p.end(),greater<int> ()); 
if(p.size()==1)
return maximum_diameter;
if(p.size()==2)
  return max(maximum_diameter,p[0]+p[1]+L); 
return max(maximum_diameter,max(p[0]+p[1]+L, p[1]+p[2]+2*L));

  }

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