/* ************************************************************************** */
/* */
/* ::: ::: ::: */
/* Problem Number: 17712 :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: js9028 <boj.kr/u/js9028> +#+ +#+ +#+ */
/* +#+ +#+ +#+ */
/* https://boj.kr/17712 #+# #+# #+# */
/* Solved: 2024/09/27 11:02:15 by js9028 ### ### ##.kr */
/* */
/* ************************************************************************** */
#include <bits/stdc++.h>
using namespace std;
#define fastio (ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL))
typedef long long ll;
typedef long double lld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int MAXSIZE = 2000000;
const long long INF = 1e18 + 5;
const double EPSILON = 1e-14;
const ll DIV = 2000003;
const long double pi = 3.14159265358979323846264338327950288419716939937510L;
int n;
pll adj[101010];
vector<pll> radj[101010];
ll mx[101010], sum[101010];
ll ans;
vector<int> cycle;
int vst[101010];
bool iscycle[101010];
ll cycle_sum;
ll cycle_val[101010];
int nt = 1;
int get_cycle(int cur)
{
vst[cur] = nt;
int ret = 0;
for (auto nxt : radj[cur])
{
if (vst[nxt.first] == nt)
{
iscycle[cur] = 1;
cycle.push_back(cur);
cycle_sum += adj[cur].second;
cycle_val[cur] = nxt.second;
return nxt.first;
}
else if (vst[nxt.first])
return 0;
ret = max(ret, get_cycle(nxt.first));
if (ret)
{
cycle_sum += adj[cur].second;
cycle_val[cur] = nxt.second;
iscycle[cur] = 1;
cycle.push_back(cur);
if (ret == cur)
return 0;
return ret;
}
}
if (ret == cur)
return 0;
return ret;
}
int main()
{
fastio;
cin >> n;
for (int i = 1; i <= n; i++)
{
ll a, b;
cin >> a >> b;
adj[i] = {a, b};
radj[a].push_back({i, b});
mx[a] = max(mx[a], b);
sum[a] += b;
}
for (int i = 1; i <= n; i++)
{
cycle_sum = 0;
cycle.clear();
if (vst[i])
continue;
get_cycle(i);
nt++;
if (cycle.size() == n)
break;
if (cycle.empty())
continue;
if (adj[cycle[0]].first != cycle.back())
continue;
ll tm = INF;
ll psm = -cycle_sum;
for (int j : cycle)
{
psm += sum[j];
ll tx = 0;
for (auto nx : radj[j])
{
if (iscycle[nx.first] == 0)
{
tx = max(tx, nx.second);
}
}
tm = min(tm, -tx + cycle_val[j]);
}
psm += tm;
ans += psm;
}
for (int i = 1; i <= n; i++)
{
if (iscycle[i])
continue;
ans += sum[i] - mx[i];
}
cout << ans;
return 0;
}
Compilation message
telegraph.cpp: In function 'int main()':
telegraph.cpp:95:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
95 | if (cycle.size() == n)
| ~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
