#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010101
#define MAXQ 101010
#define INF 1'000'000'100
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
#define TC 1
int vis[MAX];
int A[MAX], C[MAX];
ll dp[2][MAX];
vector<int> adj[MAX];
int chk[MAX];
void dfs(int x) {
vis[x] = 1;
int mx = 0;
for (auto v : adj[x]) if (!vis[v]) {
dfs(v);
dp[0][x] += dp[1][v];
mx = max(mx, C[v]);
}
dp[1][x] = dp[0][x] + mx;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N;
cin >> N;
int i;
ll sum = 0;
for (i = 1; i <= N; i++) {
cin >> A[i] >> C[i];
sum += C[i];
adj[A[i]].push_back(i);
}
vector<int> cyc;
ll ans = 0;
for (i = 1; i <= N; i++) if (!vis[i]) {
cyc.clear();
int v = i;
while (1) {
cyc.push_back(v);
vis[v] = 1;
v = A[v];
if (vis[v]) {
vector<int> cv;
int chk = 0;
for (auto x : cyc) {
if (x == v) chk = 1;
if (chk) cv.push_back(x);
}
cyc = cv;
break;
}
}
if (cyc.size() == N) {
cout << 0;
return 0;
}
for (auto x : cyc) chk[x] = 1;
for (auto x : cyc) dfs(x);
ll mn = 1e18;
for (auto x : cyc) {
int n = A[x];
ll a, b;
a = dp[0][n] + C[x];
b = dp[1][n];
ll m = max(a, b);
mn = min(mn, m - b);
ans += m;
}
ans -= mn;
}
cout << sum - ans;
}
Compilation message
telegraph.cpp: In function 'int main()':
telegraph.cpp:65:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
65 | if (cyc.size() == N) {
| ~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
33112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
33112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
33112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
33112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
