| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 167528 | DavidDamian | Dreaming (IOI13_dreaming) | C++11 | 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 "dreaming.h"
#include<vector>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
bool byGreater(long long int a,long long int b)
{
return a>b;
}
struct edge
{
long long int from,to;
long long int w;
};
vector<edge> adjList[100005];
long long int far[100005]; //Stores the minimum longest distance for each tree
long long int color[100005];
long long int d[2][100005];
queue<long long int> Q;
long long int bfs(long long int s,long long int op,long long int c)
{
color[s]=c;
d[op][s]=0;
Q.push(s);
long long int farthest_node;
long long int maximum=0;
while(Q.size()){
long long int u=Q.front();Q.pop();
for(edge e: adjList[u]){
long long int v=e.to;
if(color[v]!=c){
color[v]=c;
d[op][v]=d[op][u]+e.w;
if(d[op][v]>maximum){
maximum=d[op][v];
farthest_node=v;
}
Q.push(v);
}
}
}
return farthest_node;
}
long long int getOptimumDistance(long long int s,long long int c)
{
color[s]=c;
long long int minimumD=1000000000;
Q.push(s);
while(Q.size()){
long long int u=Q.front();Q.pop();
if(max(d[0][u],d[1][u])<minimumD){
minimumD=max(d[0][u],d[1][u]);
}
for(edge e: adjList[u]){
long long int v=e.to;
if(color[v]!=c){
color[v]=c;
Q.push(v);
}
}
}
return minimumD;
}
long long int travelTime(long long int N, long long int M, long long int L, long long int A[], long long int B[], long long int T[]) {
for(long long int i=0;i<M;i++){
edge e={A[i],B[i],T[i]};
adjList[e.from].push_back(e);
swap(e.from,e.to);
adjList[e.from].push_back(e);
}
long long int answer=0;
long long int max_diameter=0;
long long int c=1;
long long int trees=0;
for(long long int u=0;u<N;u++){
if(color[u]!=0) continue;
long long int a=bfs(u,1,c++);
long long int b=bfs(a,0,c++);
bfs(b,1,c++);
max_diameter=max(max_diameter,d[1][a]);
far[trees++]=getOptimumDistance(u,c++);
}
sort(far,far+trees,byGreater);
if(trees==1){
answer=max_diameter;
}
else if(trees==2){
answer=max(max_diameter,far[0]+L+far[1]); //Path joining yourself with another tree
}
else{
answer=max(max_diameter,
max(far[0]+L+far[1],far[1]+L+L+far[2])); //Path joining yourself with another tree
//and joining other two trees whose path passes for you
}
return answer;
}