This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* ************************************************************************** */
/* */
/* ::: ::: ::: */
/* Problem Number: 17712 :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: js9028 <boj.kr/u/js9028> +#+ +#+ +#+ */
/* +#+ +#+ +#+ */
/* https://boj.kr/17712 #+# #+# #+# */
/* Solved: 2024/09/28 00:01:54 by js9028 ### ### ##.kr */
/* */
/* ************************************************************************** */
#include <iostream>
#include <memory.h>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>
#include <tuple>
#define fastio (ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL))
using namespace std;
typedef long long ll;
const long long INF = 1e18 + 5;
int n;
pair<int, ll> nxt[101010];
vector<pair<int, ll>> radj[101010];
pair<ll, ll> cost[101010];
vector<vector<int>> cyl;
bool iscycle[101010];
ll eval[101010];
int tn[101010];
int nt = 1;
vector<int> tmp;
int get_cycle(int cur)
{
tn[cur] = nt;
int nx = nxt[cur].first;
if (tn[nx] == nt)
{
tmp.push_back(cur);
iscycle[cur] = 1;
eval[nx] = nxt[cur].second;
}
else if (tn[nx])
{
return 0;
}
int ret = get_cycle(nx);
if (ret)
{
tmp.push_back(cur);
iscycle[cur] = 1;
eval[nx] = nxt[cur].second;
if (ret == cur)
ret = 0;
}
return ret;
}
ll esum[101010];
ll me[101010];
int main()
{
fastio;
cin >> n;
for (int i = 1; i <= n; i++)
{
int a, b;
cin >> a >> b;
nxt[i] = {a, b};
radj[a].push_back({i, b});
esum[a] += b;
me[a] = max(me[a], (ll)b);
}
for (int i = 1; i <= n; i++)
{
if (!tn[i])
{
tmp.clear();
get_cycle(i);
cyl.push_back(tmp);
nt++;
}
}
ll ans = 0;
for (int i = 1; i <= n; i++)
{
if (!iscycle[i])
{
ans += esum[i] - me[i];
}
}
for (auto &v : cyl)
{
ll sum = 0;
for (int i : v)
{
ll mx = 0;
cost[i].first = esum[i] - me[i];
for (auto nx : radj[i])
{
if (!iscycle[nx.first])
mx = max(mx, nx.second);
}
cost[i].second = esum[i] + eval[i] - mx;
sum += cost[i].first;
}
ll t = INF;
for (int i : v)
{
t = min(t, sum - cost[i].first + cost[i].second);
}
ans += t;
}
cout << ans;
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... |