This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* There's someone in my head but it's not me */
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 1e6 + 1;
int n, bads[N / 2], rt[N], P[N], out[N], w[N], R, ptrb, ptrv, b; ll A[N], ret[N], H[N], S;
vector<int> adj[N]; bitset<N> C;
int Find(int v) {
return !rt[v] ? v : rt[v] = Find(rt[v]);
}
int Union(int v, int u) {
u = Find(u), v = Find(v);
if (u == v) return 1;
rt[u] = v;
return 0;
}
void preDFS(int v, int tr, int p = -1) {
if (!~b || H[b] < H[v]) b = v;
adj[v].push_back(v);
for (int &id : adj[v]) {
int u = out[id] ^ id ^ v;
if ((!C[u] || u == tr) && u != p)
H[u] = H[v] + w[id], preDFS(u, tr, v);
}
adj[v].pop_back();
}
void cycDFS(int v, int tr, int p = -1) {
adj[v].push_back(v);
for (int &id : adj[v]) {
if (id != tr) {
int u = out[id] ^ id ^ v;
if (u != p) P[u] = id, cycDFS(u, tr, v);
}
}
adj[v].pop_back();
}
ll CYC(int &v, int p = -1) {
ll ans = -1e18; adj[v].push_back(v);
for (int &id : adj[v]) {
int u = out[id] ^ id ^ v;
if (C[u] && u != p && u != R) {
H[u] = H[v] + w[id], ans = CYC(u, v);
break;
}
}
adj[v].pop_back();
ret[Find(v)] = max(ret[Find(v)], ans + A[v] - H[v]);
return max(ans, A[v] + H[v]);
}
ll CYC2(int &v, int p = -1) {
ll ans = -1e18; adj[v].push_back(v);
for (int &id : adj[v]) {
int u = out[id] ^ id ^ v;
if (C[u] && u != p && u != R) {
ans = CYC2(u, v);
break;
}
}
adj[v].pop_back();
ret[Find(v)] = max(ret[Find(v)], ans + A[v] + H[v]);
return max(ans, S - H[v] + A[v]);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &out[i], &w[i]);
adj[out[i]].push_back(i);
if (Union(i, out[i]))
bads[ptrb++] = i;
}
for (int i = 0; i < ptrb; i++) {
int &id = bads[i];
cycDFS(out[id], id);
int v = id; C[out[id]] = 1;
while (P[v])
C[v] = 1, v = out[P[v]] ^ P[v] ^ v;
}
for (int i = 1; i <= n; i++) {
if (!C[i]) continue;
b = -1, preDFS(i, i);
A[i] = H[b]; int u = b;
H[b] = 0, b = -1, preDFS(u, i);
ret[Find(i)] = max(ret[Find(i)], H[b]);
}
ll res = 0;
for (int i = 0; i < ptrb; i++) {
R = bads[i];
H[R] = 0; S = w[R];
int v = R;
while (P[v])
S += w[P[v]], v = P[v] ^ v ^ out[P[v]];
CYC(R), CYC2(R);
res += ret[Find(R)];
}
printf("%lld\n", res);
return 0;
}
Compilation message (stderr)
islands.cpp: In function 'int main()':
islands.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
79 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
islands.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
81 | scanf("%d%d", &out[i], &w[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |