| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1315650 | jump | Dreaming (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
//#include <bits/stdc++.h>
//#include "dreaming.h"
#include <vector>
#include <queue>
#include <iostream>
#include <limits.h>
#define int long long
int maxdist1[100010];
int maxdist2[100010];
int maxdist3[100010];
std::vector<std::vector<std::pair<int,int>>> adj;
std::vector<int> currentNum;
void bfs(int start){
std::queue<std::pair<int,int>> q;
q.push({start,0});
maxdist1[start]=0;
while(!q.empty()){
int curr = q.front().first;
currentNum.push_back(curr);
int currw = q.front().second;
q.pop();
for(auto [to,w]:adj[curr]){
if(maxdist1[to]!=-1){
maxdist1[to]=currw+w;
q.push({to,currw+w});
}
}
}
}
void bfs2(int start){
std::queue<std::pair<int,int>> q;
q.push({start,0});
maxdist2[start]=0;
while(!q.empty()){
int curr = q.front().first;
//currentNum.push_back(curr);
int currw = q.front().second;
q.pop();
for(auto [to,w]:adj[curr]){
if(maxdist2[to]!=-1){
maxdist2[to]=currw+w;
q.push({to,currw+w});
}
}
}
}
void bfs3(int start){
std::queue<std::pair<int,int>> q;
q.push({start,0});
maxdist3[start]=0;
while(!q.empty()){
int curr = q.front().first;
//currentNum.push_back(curr);
int currw = q.front().second;
q.pop();
for(auto [to,w]:adj[curr]){
if(maxdist3[to]!=-1){
maxdist3[to]=currw+w;
q.push({to,currw+w});
}
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj.resize(N);
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]});
}
for(int i=0;i<N;i++){
maxdist1[i]=-1;
maxdist2[i]=-1;
maxdist3[i]=-1;
}
std::vector<int> value;
for(int i=0;i<N;i++){
if(maxdist1[i]==-1){
bfs(i);
int nodeA=i,distA=0;
for(auto vNode:currentNum){
if(maxdist1[vNode]>distA){
nodeA=vNode;
distA=maxdist1[vNode];
}
}
bfs2(nodeA);
int nodeB=i,distB=0;
for(auto vNode:currentNum){
if(maxdist2[vNode]>distB){
nodeB=vNode;
distB=maxdist2[vNode];
}
}
bfs3(nodeB);
int minmax=1e18;
for(auto vNode:currentNum){
minmax=std::min(minmax,maxdist2[vNode]+maxdist3[vNode]);
}
currentNum.resize(0);
value.push_back(minmax);
}
}
std::sort(value.begin(),value.end());
int max=value.back();
if(value.size()>=2){
max=std::max(max,value[value.size()-2]+L);
}
return max;
}