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"
#pragma GCC optimize ("Ofast")
using namespace std;
const int N=100005;
vector<pair<int,int>> v[N];
vector<bool> vis(N,0);
vector<int> diameter(N,0);
vector<int> center(N,0);
vector<int> dist(N,-1);
vector<int> path;
pair<int,int> get_last(int a)
{
vector<int> mod;
dist[a]=0;
queue<int> q;
q.push(a);
int last=a;
while(!q.empty())
{
int e=q.front();
q.pop();
mod.push_back(e);
vis[e]=1;
for(pair<int,int> p:v[e])
{
int to=p.first;
if(dist[to]!=-1) continue;
dist[to]=dist[e]+p.second;
q.push(to);
if(dist[to]>dist[last]) last=to;
}
}
for(int i=0;i<(int)mod.size();i++) dist[mod[i]]=-1;
return make_pair(last,dist[last]);
}
bool get_path(int a,int p,int b)
{
if(a==b) return 1;
for(pair<int,int> temp:v[a])
{
int to=temp.first;
if(to==p) continue;
if(get_path(to,a,b))
{
path.push_back(temp.second);
return 1;
}
}
return 0;
}
void get_center(int a,int id)
{
int one,two,len;
tie(one,ignore)=get_last(a);
tie(two,len)=get_last(one);
diameter[id]=len;
path.clear();
get_path(one,-1,two);
int best=diameter[id];
int sum=0;
for(int i=0;i<(int)path.size();i++)
{
sum+=path[i];
best=min(best,max(sum,diameter[id]-sum));
}
center[id]=best;
}
int solve(int n,int l)
{
int id=0;
for(int i=0;i<n;i++) if(vis[i]==0) get_center(i,id++);
int res=0;
vector<pair<int,int>> root;
for(int i=0;i<id;i++)
{
res=max(res,diameter[i]);
root.push_back(make_pair(center[i],i));
}
sort(root.begin(),root.end(),greater<pair<int,int>>());
if(id>1) res=max(res,root[0].first+l+root[1].first);
if(id>2) res=max(res,root[1].first+2*l+root[2].first);
return res;
}
int travelTime(int n,int m,int l,int a[],int b[],int t[])
{
for(int i=0;i<m;i++)
{
v[a[i]].push_back(make_pair(b[i],t[i]));
v[b[i]].push_back(make_pair(a[i],t[i]));
}
return solve(n,l);
}
/*int main()
{
freopen("C:\\Users\\Benja\\Downloads\\ioi2013tests\\dreaming\\two-sticks-9.in","r",stdin);
int n,m,l;
scanf("%d%d%d",&n,&m,&l);
for(int i=0;i<m;i++)
{
int a,b,t;
scanf("%d%d%d",&a,&b,&t);
v[a].push_back(make_pair(b,t));
v[b].push_back(make_pair(a,t));
}
printf("%d\n",solve(n,l));
return 0;
}*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |