Submission #1312678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312678		kevin264	Dreaming (IOI13_dreaming)	C++20	18 / 100	109 ms	31824 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);
}

int take_center(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 center=-1;
for(auto number : g){
   // cout<<i<<": "<<dista[i]<<" "<<distb[i]<<' '<<max(dista[i],distb[i])<<endl;
   int i=number.ff;
center=center==-1 or max(dista[i],distb[i])<center ? max(dista[i],distb[i]) : center;
}
return center;
}

int travelTime(int N, int M, int L, 
  int A[], int B[], int T[]){
    if(M==N-1){
    unordered_map<int,vector<pii> > g;
      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]});
  }
  pair<int,u_m> pr=djikstra(0,g);
  int a=pr.ff;
  pr=djikstra(a,g); 
  return pr.ss[pr.ff]; 
  }
  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;
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});
        }
      }
    }
    p.push_back(take_center(current)); 
   }
}
sort(p.begin(),p.end(),greater<int> ()); 

if(p.size()==1)
  return p[0];
if(p.size()==2)
  return p[0]+p[1]+L; 
return max(p[0]+p[1]+L, p[1]+p[2]+2*L);

  }

/*int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0); 
    int n,m,l;
    cin>>n>>m>>l;
   int A[n], B[n], T[n]; 
    for(int i=0;i<m;i++) {
        int a,b,t;
        cin>>a>>b>>t;
      A[i]=a; B[i]=b; T[i]=t;
      }
    cout<<travelTime(n,m,l,A,B,T)<<endl;
    return 0;
}*/

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