#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Edge {
int a, b, cost;
bool seen = false;
};
const int N = (int) 1e6 + 7;
const ll INF = (ll) 1e18;
int n;
int parrent[N];
Edge graph_edges[N];
vector<int> g[N], verts;
bool vis[N];
int dep[N];
int epar[N];
vector<int> geallonp(int a, int b) {
vector<int> p1, p2;
while (a != b) {
if (dep[a] > dep[b]) {
p1.push_back(a);
a = parrent[a];
} else {
p2.push_back(b);
b = parrent[b];
}
}
p1.push_back(a);
reverse(p2.begin(), p2.end());
for (auto &x : p2) {
p1.push_back(x);
}
return p1;
}
vector<int> geallonpedges(int a, int b) {
vector<int> p1, p2;
while (a != b) {
if (dep[a] > dep[b]) {
p1.push_back(epar[a]);
a = parrent[a];
} else {
p2.push_back(epar[b]);
b = parrent[b];
}
}
reverse(p2.begin(), p2.end());
for (auto &x : p2) {
p1.push_back(x);
}
return p1;
}
bool blocked[N];
ll under[N];
ll bbpath[N];
void dfs(int a) {
for (auto &i : g[a]) {
int b = graph_edges[i].a + graph_edges[i].b - a;
if (blocked[b] || b == parrent[a]) {
continue;
}
dfs(b);
bbpath[a] = max(bbpath[a], bbpath[b]);
bbpath[a] = max(bbpath[a], under[b] + graph_edges[i].cost + under[a]);
under[a] = max(under[a], under[b] + graph_edges[i].cost);
}
}
ll sum[N];
bool v2[N];
ll solveComponent(int rootVertex) {
ll sol = 0;
verts.clear();
queue<int> q;
q.push(rootVertex);
vis[rootVertex] = true;
while (!q.empty()) {
int a = q.front();
q.pop();
verts.push_back(a);
for (auto &i : g[a]) {
int b = graph_edges[i].a + graph_edges[i].b - a;
if (!vis[b]) {
dep[b] = 1 + dep[a];
epar[b] = i;
vis[b] = true;
q.push(b);
parrent[b] = a;
graph_edges[i].seen = true;
}
}
}
vector<int> nnseeng;
for (auto &v : verts) {
for (auto &i : g[v]) {
if (!graph_edges[i].seen) {
graph_edges[i].seen = true;
nnseeng.push_back(i);
}
}
}
{
int index = nnseeng[0];
int a = graph_edges[index].a;
int b = graph_edges[index].b;
int cost = graph_edges[index].cost;
vector<int> path = geallonp(a, b);
vector<int> edges = geallonpedges(a, b);
vector<ll> value;
edges.push_back(index);
vector<int> ord;
for (auto &v : path) {
blocked[v] = true;
q.push(v);
v2[v] = true;
}
while (!q.empty()) {
int a = q.front();
q.pop();
ord.push_back(a);
for (auto &i : g[a]) {
int b = graph_edges[i].a + graph_edges[i].b - a;
if (!v2[b]) {
parrent[b] = a;
q.push(b);
v2[b] = true;
}
}
}
for (auto &v : path) {
dfs(v);
sol = max(sol, bbpath[v]);
value.push_back(under[v]);
}
ll total = 0;
for (auto &i : edges) {
total += graph_edges[i].cost;
}
ll cur = 0;
for (int i = 1; i <= (int) edges.size(); i++) {
cur += graph_edges[edges[i - 1]].cost;
sum[i] = cur;
}
int y = (int) value.size();
ll c1 = -INF, c2 = -INF;
for (int r = 0; r < y; r++) {
ll b1 = c1 + sum[r] + value[r];
ll b2 = c2 + total + value[r] - sum[r];
c1 = max(c1, value[r] - sum[r]);
c2 = max(c2, sum[r] + value[r]);
sol = max(sol, b1);
sol = max(sol, b2);
}
}
return sol;
}
signed main() {
/// L < P
ios::sync_with_stdio(0); cin.tie(0);
///freopen ("input2", "r", stdin);
cin >> n;
for (int i = 1; i <= n; i++) {
int j, c;
cin >> j >> c;
graph_edges[i].a = i;
graph_edges[i].b = j;
graph_edges[i].cost = c;
}
for (int i = 1; i <= n; i++) {
g[graph_edges[i].a].push_back(i);
g[graph_edges[i].b].push_back(i);
}
ll sol = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
sol += solveComponent(i);
}
}
cout << sol << "\n";
return 0;
}
Compilation message
islands.cpp: In function 'll solveComponent(int)':
islands.cpp:117:9: warning: unused variable 'cost' [-Wunused-variable]
117 | int cost = graph_edges[index].cost;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
39500 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
39476 KB |
Output isn't correct |
| 3 |
Correct |
18 ms |
39428 KB |
Output is correct |
| 4 |
Incorrect |
18 ms |
39500 KB |
Output isn't correct |
| 5 |
Correct |
17 ms |
39516 KB |
Output is correct |
| 6 |
Incorrect |
18 ms |
39508 KB |
Output isn't correct |
| 7 |
Incorrect |
17 ms |
39464 KB |
Output isn't correct |
| 8 |
Correct |
18 ms |
39500 KB |
Output is correct |
| 9 |
Incorrect |
17 ms |
39416 KB |
Output isn't correct |
| 10 |
Correct |
17 ms |
39500 KB |
Output is correct |
| 11 |
Correct |
18 ms |
39472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
39612 KB |
Output is correct |
| 2 |
Correct |
18 ms |
39552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
39628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
40540 KB |
Output is correct |
| 2 |
Correct |
40 ms |
42432 KB |
Output is correct |
| 3 |
Incorrect |
28 ms |
41164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
43704 KB |
Output is correct |
| 2 |
Correct |
49 ms |
45720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
54396 KB |
Output is correct |
| 2 |
Correct |
99 ms |
55332 KB |
Output is correct |
| 3 |
Correct |
117 ms |
61528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
63336 KB |
Output is correct |
| 2 |
Correct |
180 ms |
81828 KB |
Output is correct |
| 3 |
Correct |
194 ms |
80136 KB |
Output is correct |
| 4 |
Correct |
236 ms |
99032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
291 ms |
102588 KB |
Output is correct |
| 2 |
Correct |
878 ms |
119464 KB |
Output is correct |
| 3 |
Correct |
263 ms |
88640 KB |
Output is correct |
| 4 |
Correct |
350 ms |
112024 KB |
Output is correct |
| 5 |
Correct |
334 ms |
111040 KB |
Output is correct |
| 6 |
Incorrect |
1111 ms |
104148 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
314 ms |
93992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
