Codeforces Round #427 (Div. 2), problem: (F) Roads in the Kingdom Solution In C/C++

#include <bits/stdc++.h>

using namespace std;

int n;

int to[500000], pre[500000], cost[500000], last[250000], en;

long long wxs;

void addedge(int f, int t, int w)
{
to[++en] = t;
cost[en] = w;
pre[en] = last[f];
last[f] = en;
}

int Stack[250000], vis[250000], top;

int ring[250000], rs;

long long val[250000], edge[250000];

bool dfs(int now, int p)
{
Stack[++top] = now;
vis[now] = top;
for (int i = last[now]; i; i = pre[i])
{
if (to[i] == p)
{
continue;
}
if (vis[to[i]] > 0)
{
for (int j = vis[to[i]]; j <= top; ++j)
{
ring[++rs] = Stack[j];
}
return 1;
}
if (dfs(to[i], now))
{
return 1;
}
}
–top;
vis[now] = 2147483647;
return 0;
}

int taboo1, taboo2;

long long dfs2(int now, int p)
{
long long fir = 0, sec = 0;
for (int i = last[now]; i; i = pre[i])
{
if (to[i] == p)
{
continue;
}
if (to[i] == taboo1)
{
continue;
}
if (to[i] == taboo2)
{
continue;
}
long long th = dfs2(to[i], now) + cost[i];
if (th >= fir)
{
sec = fir;
fir = th;
} else if (th > sec)
{
sec = th;
}
}
wxs = max(wxs, fir + sec);
return fir;
}

long long to_l[250000], to_r[250000];
long long mx_l[250000], mx_r[250000];

long long ans;

int main()
{
scanf(“%d”, &n);
for (int i = 1; i <= n; ++i)
{
int u, v, w;
scanf(“%d%d%d”, &u, &v, &w);
addedge(u, v, w);
addedge(v, u, w);
}
dfs(1, 0);
ring[0] = ring[rs];
ring[rs + 1] = ring[1];
long long sum = 0;
for (int i = 1; i <= rs; ++i)
{
taboo1 = ring[i – 1];
taboo2 = ring[i + 1];
val[i] = dfs2(ring[i], 0);
for (int j = last[ring[i]]; j; j = pre[j])
{
if (to[j] == ring[i – 1])
{
edge[i – 1] = cost[j];
sum += cost[j];
}
}
}
edge[rs] = edge[0];
val[0] = val[rs];
val[rs + 1] = val[1];
long long tmp = 0, tmp2 = 0;
for (int i = 1; i <= rs; ++i)
{
to_l[i] = max(to_l[i – 1], tmp + val[i]);
mx_l[i] = max(mx_l[i – 1], tmp2 + val[i]);
tmp += edge[i];
tmp2 = max(tmp2, val[i]) + edge[i];
}
tmp = tmp2 = 0;
for (int i = rs; i >= 1; –i)
{
to_r[i] = max(to_r[i + 1], tmp + val[i]);
mx_r[i] = max(mx_r[i + 1], tmp2 + val[i]);
tmp += edge[i – 1];
tmp2 = max(tmp2, val[i]) + edge[i – 1];
}
ans = mx_l[rs];
for (int i = 1; i < rs; ++i)
{
long long nans = max(to_l[i] + to_r[i + 1] + edge[0], max(mx_l[i], mx_r[i + 1]));
ans = min(ans, nans);
}
ans = max(ans, wxs);
cout << ans << endl;
}