#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 1000000;
int const inf = 1000000000;
int edge[5 + nmax][3], seen[5 + nmax];
vector<int> g[5 + nmax];
vector<int> st, cycle;
int in_stack[5 + nmax];
int oth(int node, int id){
return edge[id][0] + edge[id][1] - node;
}
bool exist(int node, int id){
return ((edge[id][0] == node) || (edge[id][1] == node));
}
void mark(int node){
if(seen[node] == 1)
return ;
seen[node] = 1;
for(int h = 0; h < g[node].size(); h++)
mark(oth(node, g[node][h]));
}
void dfs(int node, bool &done){
if(in_stack[node] == 1){
cycle.push_back(st.back());
st.pop_back();
while(exist(node, st.back()) == 0){
cycle.push_back(st.back());
st.pop_back();
}
cycle.push_back(st.back());
st.pop_back();
done = 1;
}
in_stack[node] = 1;
for(int h = 0; h < g[node].size(); h++){
int id = g[node][h];
if(done == 1)
return ;
if(st.size() == 0 || st.back() != id) {
st.push_back(id);
dfs(oth(node, id), done);
st.pop_back();
}
}
in_stack[node] = 0;
}
ll dp[1 + nmax];
ll maxdist(int node, int parent ){
for(int h = 0; h < g[node].size(); h++){
int id = g[node][h];
int to = oth(node, id);
if(seen[to] < 2 && parent != to) {
maxdist(to, node);
dp[node] = max(dp[node], dp[to] + edge[id][2]);
}
}
return dp[node];
}
vector<int> path;
ll solve(int node){
cycle.clear();
st.clear();
path.clear();
mark(node);
bool done = 0;
dfs(node, done);
ll sum = 0;
for(int i = 0; i < cycle.size(); i++) {
int id = cycle[i];
seen[edge[id][0]] = 2;
seen[edge[id][1]] = 2;
sum += edge[id][2];
}
if(exist(edge[cycle[0]][0], cycle[1]) == 1)
path.push_back(edge[cycle[0]][0]);
else
path.push_back(edge[cycle[0]][1]);
for(int i = 1; i < cycle.size(); i++)
path.push_back(oth(path.back(), cycle[i]));
ll result = 0, smax1 = -inf, smax2 = -inf, part = 0;
for(int i = 0; i < path.size(); i++){
maxdist(path[i], 0);
if(0 < i) {
part += edge[cycle[i]][2];
result = max(result, dp[path[i]] + part + smax1);
result = max(result, dp[path[i]] + sum - part + smax2);
}
smax1 = max(smax1, dp[path[i]] - part);
smax2 = max(smax2, dp[path[i]] + part);
}
return result;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
edge[i][0] = i;
cin >> edge[i][1] >> edge[i][2];
g[edge[i][0]].push_back(i);
g[edge[i][1]].push_back(i);
}
ll result = 0;
for(int i = 1;i <= n; i++)
if(seen[i] == 0) {
result += solve(i);
}
cout << result;
return 0;
}
Compilation message
islands.cpp: In function 'void mark(int)':
islands.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++)
~~^~~~~~~~~~~~~~~~
islands.cpp: In function 'void dfs(int, bool&)':
islands.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++){
~~^~~~~~~~~~~~~~~~
islands.cpp: In function 'll maxdist(int, int)':
islands.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++){
~~^~~~~~~~~~~~~~~~
islands.cpp: In function 'll solve(int)':
islands.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < cycle.size(); i++) {
~~^~~~~~~~~~~~~~
islands.cpp:106:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < cycle.size(); i++)
~~^~~~~~~~~~~~~~
islands.cpp:111:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < path.size(); i++){
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
23936 KB |
Output isn't correct |
| 3 |
Correct |
18 ms |
23936 KB |
Output is correct |
| 4 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
18 ms |
23808 KB |
Output is correct |
| 6 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 7 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 8 |
Correct |
18 ms |
23808 KB |
Output is correct |
| 9 |
Correct |
18 ms |
23808 KB |
Output is correct |
| 10 |
Incorrect |
18 ms |
23936 KB |
Output isn't correct |
| 11 |
Correct |
17 ms |
23808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
23936 KB |
Output is correct |
| 2 |
Correct |
19 ms |
23936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
23936 KB |
Output is correct |
| 2 |
Correct |
20 ms |
24192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
24936 KB |
Output is correct |
| 2 |
Correct |
38 ms |
27128 KB |
Output is correct |
| 3 |
Correct |
30 ms |
25088 KB |
Output is correct |
| 4 |
Incorrect |
23 ms |
24448 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
28456 KB |
Output is correct |
| 2 |
Correct |
58 ms |
31096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
37368 KB |
Output is correct |
| 2 |
Correct |
116 ms |
41716 KB |
Output is correct |
| 3 |
Correct |
155 ms |
49804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
182 ms |
47992 KB |
Output is correct |
| 2 |
Correct |
241 ms |
68276 KB |
Output is correct |
| 3 |
Correct |
257 ms |
74212 KB |
Output is correct |
| 4 |
Correct |
318 ms |
90312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
348 ms |
77408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
471 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
