| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 747584 | coding_snorlax | Dreaming (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long int;
ll dis1[200002] = {0};
ll dis2[200002] = {0};
vector<int> vis_node;
ll vis[200002] = {0};
ll Process[200002] = {0};
int cost;
void init(){
for(int i:vis_node){
vis[i]=0;
dis2[i]=0;
Process[i] = 1;
}
//vis_node.clear();
}
vector<pair<ll,ll>> G[100002];
int dfs_1(int node,int father,int weight){
//cout << node << " ";
vis_node.push_back(node);
vis[node]=1;
dis1[node] = dis1[father] + weight;
for(auto i:G[node]){
if(!vis[i.first]) dfs_1(i.first,node,i.second);
}
}
int dfs_2(int node,int father,int weight){
vis_node.push_back(node);
vis[node]=1;
dis2[node] = dis2[father] + weight;
for(auto i:G[node]){
if(!vis[i.first]) dfs_2(i.first,node,i.second);
}
}
ll Node_f(int node){
init();
dfs_1(node,node,0);
int Max = 0;
int Max_place = 0;
for(int i:vis_node){
if(Max < dis1[i]){
Max = dis1[i];
Max_place = i;
}
}
init();
dfs_2(Max_place,Max_place,0);
for(int i:vis_node){
dis1[i] = dis2[i];
}
Max = 0; Max_place = 0;
for(int i:vis_node){
if(Max < dis1[i]){
Max = dis1[i];
Max_place = i;
}
}
init();
dfs_2(Max_place,Max_place,0);
ll answer = 1500000000;
for(int i:vis_node){
dis1[i] = max(dis1[i],dis2[i]);
answer = min(dis1[i],answer);
}
//cout << endl;
return answer;
}
int travelTime(int N,int M,int L,vector<int> A,vector<int> B,vector<int> T){
for(int i=0;i<M;i++){
G[A[i]].push_back(make_pair(B[i],T[i]));
G[B[i]].push_back(make_pair(A[i],T[i]));
}
cost = L;
vector<int> List;
for(int i=0;i<M;i++){
if(!Process[i]){
List.push_back(Node_f(i));
//cout << i << " " << Node_f(i) << endl;
//for(int j:vis_node) cout << j << " ";
//cout << endl;
vis_node.clear();
}
}
sort(List.begin(),List.end());
int answer = List.back();
List.pop_back();
return answer+List.back()+L;
}