| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1096940 | rahidilbayramli | Dreaming (IOI13_dreaming) | C++17 | 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>
#define ll int
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define p_b pop_back
#define f first
#define s second
using namespace std;
const ll sz = 1e5+5, sz2 = 3e5+5;
vector<pll>g[sz];
vector<pll>ng[sz2];
ll vis[sz], vis2[sz], vis3[sz2], dis[sz2], par[sz], dist[sz], maxd = 0, rn1 = -1, rn2 = -1;
void dfs1(ll node)
{
vis[node] = 1;
for(auto [u, w] : g[node])
{
if(vis[u])
continue;
dist[u] = dist[node] + w;
if(dist[u] > maxd)
{
maxd = dist[u];
rn1 = u;
}
dfs1(u);
}
}
void dfs2(ll node)
{
vis2[node] = 1;
for(auto [u, w] : g[node])
{
if(vis2[u])
continue;
dist[u] = dist[node] + w;
par[u] = node;
if(dist[u] > maxd)
{
maxd = dist[u];
rn2 = u;
}
dfs2(u);
}
}
void dfs3(ll node)
{
vis3[node] = 1;
for(auto [u, w] : ng[node])
{
if(vis3[u])
continue;
dis[u] = dis[node] + w;
if(dis[u] > maxd)
{
maxd = dis[u];
rn1 = u;
}
dfs3(u);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(ll i = 0; i < M; i++)
{
A[i]++, B[i]++;
g[A[i]].pb({B[i], T[i]});
g[B[i]].pb({A[i], T[i]});
}
vector<pair<ll, pll>>vect;
for(ll i = 1; i <= N; i++)
{
if(!vis[i])
{
rn1 = i;
rn2 = i;
maxd = 0;
dfs1(i);
dist[rn1] = 0;
maxd = 0;
dfs2(rn1);
vect.pb({maxd, {rn1, rn2}});
}
}
vector<pll>vv;
for(auto u : vect)
{
ll rn1 = u.s.s, maxd = u.f;
vl v;
while(par[rn1] != 0)
{
v.pb(rn1);
rn1 = par[rn1];
}
ll diff = INT_MAX, sum1 = 0, sum2 = maxd;
for(auto h : v)
{
ll p = abs(dist[h] - maxd);
if(abs(dist[h] - p) < diff)
{
diff = abs(dist[h] - p);
sum1 = dist[h];
sum2 = p;
}
}
vv.pb({max(sum1, sum2), min(sum1, sum2)});
}
sort(rall(vv));
ll nval = 0;
for(auto u : vv)
{
ll a = nval + 1, b = nval + 2, c = nval + 3;
ng[a].pb({b, u.f});
ng[b].pb({a, u.f});
ng[b].pb({c, u.s});
ng[c].pb({b, u.s});
nval += 3;
}
for(ll i = 5; i < nval; i += 3)
{
ng[2].pb({i, L});
ng[i].pb({2, L});
}
maxd = 0;
rn1 = 1, rn2 = 1;
dfs3(1);
for(ll i = 1; i <= nval; i++)
vis3[i] = 0;
maxd = 0;
dis[rn1] = 0;
dfs3(rn1);
return maxd;
}
int main()
{
}