| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 315367 | tasfiq4 | 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 "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int > pii;
typedef long long int lld;
#define pi acos(-1)
#define fr(i,m,n) for(i=m;i<n;i++)
#define fu(i,m,n) for(i=m;i>=n;i--)
#define vec vector<int>
#define pb push_back
#define pp pop_back()
#define ft first
#define sd second
#define all(v) v.begin(),v.end()
#define mom(ara) memset(ara,0,sizeof(ara));
#define m1m(ara) memset(ara,-1,sizeof(ara));
#define endl "\n"
#define eps 1.19209e-07
vector<pii> adj[100010];
int visited[100010];
int mx[100010];
void get_dm(int u,int p)
{
visited[u]=1;
mx[u]=0;
for(auto v:adj[u])
{
if(v.ft==p) continue;
get_dm(v.ft,u);
mx[u]=max(mx[u],mx[v.ft]+v.sd);
}
}
pii func(int u,int p,int d)
{
int m=d,m2=0,n,l;
for(auto v:adj[u])
{
if(v.ft==p) continue;
if(mx[v.ft]>m)
{
m2=m;
m=mx[v.ft];
n=v.ft;
l=v.sd;
}
else if(mx[v.ft]>m2) m2=mx[v.ft];
}
if(m2+l<m) return func(n,u,m2+l);
return {u,m};
}
struct cmp
{
bool operator()(const pair<int,int> &a,const pair<int,int> &b) const{
return a.sd>b.sd;
}
};
pair<int, int> bfs(int n, int s) {
vector<int> dis(n+1, -1);
priority_queue<pii,vector<pii>,cmp> q;
q.push({s,0});
dis[s] = 0;
int last = n;
while (q.size()) {
int u = q.top().ft;
q.pop();
for (auto v: adj[u])
if (dis[v.ft] == -1) {
dis[v.ft] = dis[u] + v.sd;
if(dis[v.ft]>dis[last]) last=v.ft;
q.push({v.ft,v.sd});
}
}
return {last, dis[last]};
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int i,j,a,b,c,x,y,z,n,m,w,k,t;
priority_queue<pii,vector<pii>,cmp> h;
n=N;m=M;k=L;
fr(i,0,m)
{
a=A[i];b=B[i];w=T[i];
adj[a].pb({b,w});
adj[b].pb({a,w});
}
fr(i,0,n)
{
if(visited[i]) continue;
get_dm(i,-1);
h.push(func(i,-1,0));
}
while(h.size()!=1)
{
pii u=h.top();
h.pop();
pii v=h.top();
h.pop();
h.push({u.ft,max(u.sd+k,v,sd)});
}
return bfs(n, bfs(n, 0).first).second;
}