# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
174790 | FieryPhoenix | 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 <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
int N,M,L;
vector<pair<int,int>>adj[100001];
bool vis[100001];
int ans=0;
int mx,store;
int dis[100001];
int deep[100001];
vector<int>center;
void dfs1(int node, int par){
if (dis[node]>mx){
mx=dis[node];
store=node;
}
for (auto p:adj[node])
if (p.first!=par){
dis[p.first]=dis[node]+p.second;
dfs1(p.first,node);
}
}
void dfs2(int node, int par){
for (auto p:adj[node]){
if (p.first!=par){
dfs2(p.first,node);
deep[node]=max(deep[node],p.second+deep[p.first]);
}
}
}
int mn;
void dfs3(int node, int up){
vis[node]=true;
deep[node]=max(deep[node],up);
mn=min(mn,deep[node]);
multiset<int>mst;
for (auto p:adj[node])
if (!vis[p.first])
mst.insert(deep[p.first]+p.second);
for (auto p:adj[node])
if (!vis[p.first]){
mst.erase(mst.find(deep[p.first]+p.second));
if (mst.empty())
dfs3(p.first,up+p.second);
else
dfs3(p.first,max(up,*mst.rbegin())+p.second);
mst.insert(deep[p.first]+p.second);
}
}
void solve(int node){
//cout<<"SOLVE: "<<node<<endl;
mx=-1;
dfs1(node,node);
mx=-1; dis[store]=0;
dfs1(store,store);
ans=max(ans,mx);
//cout<<"DIAMETER: "<<mx<<endl;
dfs2(node,node);
mn=INF; dfs3(node,0);
center.push_back(mn);
//cout<<"CENTER: "<<mn<<endl;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
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++){
if (!vis[i])
solve(i);
}
sort(center.begin(),center.end());
for (int i=0;i+1<(int)center.size();i++)
center[i]+=L;
sort(center.begin(),center.end());
if (center.size()>=2)
ans=max(ans,center[center.size()-1]+center[center.size()-2]);
return ans;
}