| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 109916 | MetB | Islands (IOI08_islands) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <cstdlib>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <math.h>
#include <stack>
#include <vector>
#include <string.h>
#include <random>
typedef long long ll;
const ll MOD = 1e9 + 7, INF = 1e18;
using namespace std;
int n, m, is_cycle[1000000], u[1000000], p[1000000], c[1000000];
ll d[1000000][2], cost[1000000];
ll pref[2000000];
vector < pair <int, ll> > g_un[1000000], g_t[1000000];
vector < pair <int, ll> > cycle[1000000];
void dfs_traverse (ll x)
{
c[x] = 1;
for (auto to : g[x])
if (!c[to.first])
dfs_traverse (to.first);
}
bool dfs_cycle (ll x, ll par, ll color)
{
u[x] = 1;
for (auto to : g_t[x])
{
if (u[to.first] == 1)
{
ll v = x;
while (v != to.first)
{
cycle[color].emplace_back (v, cost[v]);
is_cycle[v] = true;
v = p[v];
}
cycle[color].emplace_back (to.first, to.second);
is_cycle[to.first] = true;
return true;
}
else if (!u[to.first])
{
p[to.first] = x;
cost[to.first] = to.second;
if (dfs_cycle (to.first, x, color)) return true;
}
}
u[x] = 2;
return false;
}
ll find_diameter (ll x, ll p)
{
ll sum = 0, mx = 0, smx = 0;
for (auto to : g_un[x])
if (to.first != p && !is_cycle[to.first])
{
sum = max (sum, find_diameter (to.first, x));
if (mx <= d[to.first][0] + to.second)
{
smx = mx;
mx = d[to.first][0] + to.second;
}
else smx = max (smx, d[to.first][0] + to.second);
}
d[x][0] = mx;
d[x][1] = smx;
return max (sum, mx + smx);
}
ll process (vector < pair <int, ll> > & cycle)
{
ll diameter = 0;
for (auto x : cycle)
diameter = max (diameter, find_diameter (x.first, -1));
ll s = cycle.size ();
for (ll i = 0; i < s; i++)
cycle.push_back (cycle[i]);
for (ll i = cycle.size () - 1; i >= 0; i--)
pref[i] = cycle[i].second + (i != cycle.size () - 1 ? pref[i+1] : 0);
deque < pair <ll, ll> > q_max;
for (ll i = 0; i < s - 1; i++)
{
while (!q_max.empty () && q_max.back ().first <= pref[i] + d[cycle[i].first][0])
q_max.pop_back ();
q_max.emplace_back (pref[i] + d[cycle[i].first][0], i);
}
for (ll i = s - 1; i < cycle.size (); i++)
{
ll k = q_max.front ().first;
diameter = max (diameter, k - pref[i] + d[cycle[i].first][0]);
while (!q_max.empty () && q_max.back ().first <= pref[i] + d[cycle[i].first][0])
q_max.pop_back ();
q_max.emplace_back (pref[i] + d[cycle[i].first][0], i);
while (!q_max.empty () && q_max.front ().second <= i - s + 1)
q_max.pop_front ();
}
reverse (cycle.begin(), cycle.end());
pref[cycle.size () - 1] = cycle[0].second;
for (ll i = cycle.size () - 2; i >= 0; i--)
pref[i] = pref[i + 1] + cycle[i + 1].second;
q_max.clear ();
for (ll i = 0; i < s - 1; i++)
{
while (!q_max.empty () && q_max.back ().first <= pref[i] + d[cycle[i].first][0])
q_max.pop_back ();
q_max.emplace_back (pref[i] + d[cycle[i].first][0], i);
}
for (ll i = s - 1; i < cycle.size (); i++)
{
diameter = max (diameter, q_max.front ().first - pref[i] + d[cycle[i].first][0]);
while (!q_max.empty () && q_max.back ().first <= pref[i] + d[cycle[i].first][0])
q_max.pop_back ();
q_max.emplace_back (pref[i] + d[cycle[i].first][0], i);
while (!q_max.empty () && q_max.front ().second <= i - s + 1)
q_max.pop_front ();
}
return diameter;
}
int main ()
{
cin >> n;
for (ll i = 0; i < n; i++)
{
ll x, l;
scanf ("%lld%lld", &x, &l);
g_t[i].emplace_back (x - 1, l);
g_un[x - 1].emplace_back (i, l);
}
ll color = 0;
for (ll i = 0; i < n; i++)
if (!u[i] && !c[i])
{
dfs_cycle (i, -1, ++color);
dfs_traverse (i);
}
ll ans = 0;
for (ll i = 1; i <= color; i++)
ans += process (cycle[i]);
cout << ans;
}