#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define int long long int
signed dest[1000000];
signed length[1000000];
std::vector<signed> backEdges[1000000];
std::bitset<1000000> seen;
int bestPath[1000000];
#ifdef LOCAL
#define debug std::cout
#else
#define debug std::stringstream()
#endif
void findComponent(signed node, std::vector<signed> &data) {
if (seen[node]) return;
data.push_back(node);
seen[node] = true;
findComponent(dest[node], data);
for (auto x: backEdges[node]) {
findComponent(x, data);
}
}
int treeSum(int node) {
int sum = 0;
for (auto x: backEdges[node]) {
if (!seen[x]) {
sum += length[x] + treeSum(x);
}
}
return sum;
}
int bestSingle(int node) {
if (bestPath[node] != 0) {
return bestPath[node];
}
int best = 0;
for (auto x: backEdges[node]) {
if (!seen[x]) {
best = std::max(best, length[x] + bestSingle(x));
}
}
return bestPath[node] = best;
}
int bestDouble(int node) {
int best = 0;
int secondBest = 0;
std::vector<int> back;
for (auto x: backEdges[node]) {
if (!seen[x]) {
int score = length[x] + bestSingle(x);
if (score > best) {
secondBest = best;
best = score;
} else if (score > secondBest) {
secondBest = score;
}
}
}
return best + secondBest;
}
//Best score, assuming doesn't pass through edge between start and end of cycle.
int bestA(std::vector<signed> &cycle) {
int best = 0;
int current = 0;
int bestBehind = 0;
for (int i = 0; i < cycle.size(); ++i) {
best = std::max(best, bestSingle(cycle[i]) + current + bestBehind);
bestBehind = std::max(bestBehind, bestSingle(cycle[i]) - current);
current += length[cycle[i]];
}
return best;
}
//Best score, assuming passes through edge between start and end of cycle
int bestB(std::vector<signed> &cycle) {
int current = 0;
// std::vector<int> lengthForward;
// for (int i = 0; i < cycle.size() - 1; ++i) {
// lengthForward.push_back(current);
// current += length[cycle[i]];
// }
current = 0;
std::vector<int> lengthBackward;
for (int i = 0; i < cycle.size() - 1; ++i) {
lengthBackward.push_back(current);
current += length[cycle[cycle.size() - 2 - i]];
}
for (int i = 0; i < cycle.size() - 1; ++i) {
//lengthForward[i] += bestSingle(cycle[i]);
lengthBackward[i] += bestSingle(cycle[cycle.size() - 1 - i]);
}
for (int i = 1; i < cycle.size() - 1; ++i) {
//lengthForward[i] = std::max(lengthForward[i], lengthForward[i - 1]);
lengthBackward[i] = std::max(lengthBackward[i], lengthBackward[i - 1]);
}
int best = 0;
int lengthForward = length[cycle[cycle.size() - 1]];
int bestForward = lengthForward + bestSingle(cycle[0]);
for (int i = 0; i < cycle.size() - 1; ++i) {
best = std::max(best, bestForward + lengthBackward[cycle.size() - 2 - i]);
lengthForward += length[cycle[i]];
bestForward = std::max(bestForward, lengthForward + bestSingle(cycle[i + 1]));
}
return best;
}
int componentSum(const std::vector<signed> &component) {
for (auto x: component) {
seen[x] = false;
}
int root = component[0];
while (!seen[root]) {
seen[root] = true;
root = dest[root];
}
for (auto x: component) {
seen[x] = false;
}
std::vector<signed> cycle;
cycle.push_back(root);
seen[root] = true;
for (int x = dest[root]; x != root; x = dest[x]) {
cycle.push_back(x);
seen[x] = true;
}
int best = 0;
for (auto x: component) {
best = std::max({best, bestDouble(x), bestSingle(x)});
}
best = std::max(best, bestA(cycle));
best = std::max(best, bestB(cycle));
for (auto x: component) {
seen[x] = true;
}
return best;
}
signed main() {
#ifdef LOCAL
freopen("INPUT", "r", stdin);
#else
freopen("isl.in", "r", stdin);
freopen("isl.out", "w", stdout);
#endif
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N;
std::cin >> N;
//seen = new bool[N];
for (signed i = 0; i < N; ++i) {
seen[i] = false;
signed x, l;
std::cin >> x >> l;
x--;
dest[i] = x;
length[i] = l;
backEdges[x].push_back(i);
}
int total = 0;
for (int i = 0; i < N; ++i) {
if (!seen[i]) {
std::vector<signed> component;
findComponent(i, component);
total += componentSum(component);
}
}
std::cout << total << std::endl;
}
Compilation message
islands.cpp: In function 'long long int bestA(std::vector<int>&)':
islands.cpp:72:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int i = 0; i < cycle.size(); ++i) {
| ~~^~~~~~~~~~~~~~
islands.cpp: In function 'long long int bestB(std::vector<int>&)':
islands.cpp:90:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i = 0; i < cycle.size() - 1; ++i) {
| ~~^~~~~~~~~~~~~~~~~~
islands.cpp:94:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i = 0; i < cycle.size() - 1; ++i) {
| ~~^~~~~~~~~~~~~~~~~~
islands.cpp:98:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i = 1; i < cycle.size() - 1; ++i) {
| ~~^~~~~~~~~~~~~~~~~~
islands.cpp:105:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int i = 0; i < cycle.size() - 1; ++i) {
| ~~^~~~~~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:148:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | freopen("isl.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
islands.cpp:149:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | freopen("isl.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
91084 KB |
Execution killed with signal 6 |
| 2 |
Runtime error |
69 ms |
91104 KB |
Execution killed with signal 6 |
| 3 |
Runtime error |
68 ms |
91044 KB |
Execution killed with signal 6 |
| 4 |
Runtime error |
68 ms |
91140 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
77 ms |
91068 KB |
Execution killed with signal 6 |
| 6 |
Runtime error |
70 ms |
91072 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
80 ms |
91024 KB |
Execution killed with signal 6 |
| 8 |
Runtime error |
71 ms |
91020 KB |
Execution killed with signal 6 |
| 9 |
Runtime error |
69 ms |
91056 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
70 ms |
91056 KB |
Execution killed with signal 6 |
| 11 |
Runtime error |
69 ms |
91160 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
78 ms |
91104 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
79 ms |
91056 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
71 ms |
91028 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
76 ms |
91024 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
91084 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
91136 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
91084 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
73 ms |
91140 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
