#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 1000000
typedef long long ll;
int N;
struct S{
int idx;
ll data;
};
vector<S> gp[MAX_N+1];
int a, b;
struct C{
ll a, b;
};
S from[MAX_N+1];
vector<S> c;
vector<C> cycle;
bool vst[MAX_N+1];
bool isc[MAX_N+1];
void dfs(int x){
vst[x]=true;
for(int i=0; i<gp[x].size(); i++){
if(vst[gp[x][i].idx]){
if(gp[x][i].idx!=from[x].idx && !isc[x]){
if(from[x].idx==0){
c.push_back({gp[x][i].idx, gp[x][i].data});
isc[gp[x][i].idx]=true;
c.push_back({x, from[gp[x][i].idx].data});
isc[x]=true;
}else{
int t=x;
c.push_back({gp[x][i].idx, gp[x][i].data});
isc[gp[x][i].idx]=true;
while(t!=gp[x][i].idx){
c.push_back((S){t, from[t].data});
isc[t]=true;
t=from[t].idx;
}
}
}
}else{
from[gp[x][i].idx].idx=x;
from[gp[x][i].idx].data=gp[x][i].data;
dfs(gp[x][i].idx);
}
}
}
bool vstc[MAX_N+1];
ll len[MAX_N+1];
ll dfsc(int x){
vstc[x]=true;
len[x]=0;
ll m1=0, m2=0, m=0, ret=0;
for(int i=0; i<gp[x].size(); i++){
if(!isc[gp[x][i].idx] && !vstc[gp[x][i].idx]){
ret=max(ret, dfsc(gp[x][i].idx));
m=len[gp[x][i].idx];
if(m>m1){
m2=m1; m1=m;
}else if(m>m2) m2=m;
len[x]=max(len[x], len[gp[x][i].idx]+gp[x][i].data);
}
}
return max(ret, m1+m2);
}
ll ans=0;
int main(){
scanf("%d", &N);
for(int i=1; i<=N; i++){
scanf("%d%d", &a, &b);
gp[i].push_back((S){a, (ll)b});
gp[a].push_back((S){i, (ll)b});
}
for(int i=1; i<=N; i++){
if(!vst[i]){
dfs(i);
ll ans2=0;
ll sum=0;
while(!c.empty()){
S now = c.back(); c.pop_back();
ans2=max(ans2, dfsc(now.idx));
sum+=now.data;
cycle.push_back({now.data, len[now.idx]});
}
ll m1=0, m2=0;
while(!cycle.empty()){
C now = cycle.back(); cycle.pop_back();
ans2=max(m1+now.b, m2+now.b);
m1=max(m1+now.a, now.a+now.b);
m2=max(m2-now.a, sum-now.a+now.b);
}
ans+=ans2;
}
}
printf("%lld", ans);
return 0;
}
Compilation message
islands.cpp: In function 'void dfs(int)':
islands.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[x].size(); i++){
~^~~~~~~~~~~~~
islands.cpp: In function 'll dfsc(int)':
islands.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[x].size(); i++){
~^~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
islands.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23800 KB |
Output isn't correct |
| 2 |
Runtime error |
193 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
22 ms |
23928 KB |
Output isn't correct |
| 4 |
Runtime error |
196 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 6 |
Runtime error |
189 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
190 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Incorrect |
22 ms |
23800 KB |
Output isn't correct |
| 9 |
Runtime error |
192 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
203 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 |
Correct |
21 ms |
23788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
189 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
25592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
31604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
44744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
201 ms |
62208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
454 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
470 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
