#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
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;
};
deque<C> cycle;
bool vst[MAX_N+1];
int num[MAX_N+1];
ll len[MAX_N+1];
deque<int> leaf;
ll m[MAX_N+1][3];
ll ans=0;
vector<S> gp2;
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}); num[i]++;
gp[a].push_back((S){i, (ll)b}); num[a]++;
}
for(int i=1; i<=N; i++){
if(num[i]==1){
leaf.push_back(i);
}
}
while(!leaf.empty()){
int now=leaf.front(); leaf.pop_front();
vst[now]=true;
m[now][0]=max(m[now][0], m[now][1]+m[now][2]);
for(int i=0; i<gp[now].size(); i++){
if(!vst[gp[now][i].idx]){
len[gp[now][i].idx]=max(len[gp[now][i].idx], len[now]+gp[now][i].data);
m[gp[now][i].idx][0]=max(m[gp[now][i].idx][0], m[now][0]);
if(len[now]+gp[now][i].data>m[gp[now][i].idx][1]){
m[gp[now][i].idx][2]=m[gp[now][i].idx][1];
m[gp[now][i].idx][1]=len[now]+gp[now][i].data;
}else if(len[now]+gp[now][i].data>m[gp[now][i].idx][2]){
m[gp[now][i].idx][2]=len[now]+gp[now][i].data;
}
num[gp[now][i].idx]--;
if(num[gp[now][i].idx]==1){
leaf.push_back(gp[now][i].idx);
}
}
}
}
ll ans2=0;
ll sum=0, m1, m2;
int t;
for(int i=1; i<=N; i++){
if(!vst[i]){
for(int j=0; j<gp[i].size(); j++){
if(!vst[gp[i][j].idx]){
gp2.push_back(gp[i][j]);
}
}
while(!gp[i].empty()) gp[i].pop_back();
while(!gp2.empty()){
gp[i].push_back(gp2.back()); gp2.pop_back();
}
}
}
for(int i=1; i<=N; i++){
t=i;
if(!vst[i]){
cycle.push_front({gp[i][1].idx, gp[i][1].data});
while(1){
vst[t]=true;
if(vst[gp[t][0].idx]){
if(vst[gp[t][1].idx]){
break;
}
cycle.push_front({t, gp[t][1].data});
t=gp[t][1].idx;
}else{
cycle.push_front({t, gp[t][0].data});
t=gp[t][0].idx;
}
}
ans2=0; sum=0;
for(int j=0; j<cycle.size(); j++){
sum+=cycle[j].b;
ans2=max(ans2, max(m[cycle[j].a][0], m[cycle[j].a][1]+m[cycle[j].a][2]));
}
/*while(!c.empty()){
S now = c.back(); c.pop_back();
ans2=max(ans2, max(m[now.idx][0], m[now.idx][1]+m[now.idx][2]));
sum+=now.data;
cycle.push_back({now.data, len[now.idx]});
}*/
m1 = m2 = 0;
while(!cycle.empty()){
C now = cycle.back(); cycle.pop_back();
ans2=max(ans2, max(len[now.a], max(m1+len[now.a], m2+len[now.a])));
m1=max(m1+now.b, now.b+len[now.a]);
m2=max(m2-now.b, sum-now.b+len[now.a]);
}
ans+=ans2;
}
}
printf("%lld", ans);
return 0;
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[now].size(); i++){
~^~~~~~~~~~~~~~~
islands.cpp:69:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<gp[i].size(); j++){
~^~~~~~~~~~~~~
islands.cpp:98:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<cycle.size(); j++){
~^~~~~~~~~~~~~
islands.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
islands.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
19 ms |
23800 KB |
Output is correct |
| 3 |
Correct |
19 ms |
23800 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 6 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 7 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 8 |
Correct |
22 ms |
23876 KB |
Output is correct |
| 9 |
Correct |
21 ms |
23800 KB |
Output is correct |
| 10 |
Correct |
22 ms |
23932 KB |
Output is correct |
| 11 |
Correct |
23 ms |
23772 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23936 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
25 ms |
24156 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
33 ms |
25208 KB |
Output is correct |
| 2 |
Correct |
43 ms |
27260 KB |
Output is correct |
| 3 |
Correct |
36 ms |
25820 KB |
Output is correct |
| 4 |
Correct |
28 ms |
24696 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
52 ms |
28552 KB |
Output is correct |
| 2 |
Correct |
64 ms |
31940 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
135 ms |
41592 KB |
Output is correct |
| 2 |
Correct |
119 ms |
39884 KB |
Output is correct |
| 3 |
Correct |
146 ms |
48752 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
199 ms |
56408 KB |
Output is correct |
| 2 |
Correct |
277 ms |
71408 KB |
Output is correct |
| 3 |
Correct |
272 ms |
62200 KB |
Output is correct |
| 4 |
Correct |
334 ms |
87012 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
408 ms |
103468 KB |
Output is correct |
| 2 |
Correct |
1016 ms |
125096 KB |
Output is correct |
| 3 |
Correct |
438 ms |
103800 KB |
Output is correct |
| 4 |
Correct |
517 ms |
129832 KB |
Output is correct |
| 5 |
Correct |
492 ms |
129704 KB |
Output is correct |
| 6 |
Correct |
1421 ms |
126244 KB |
Output is correct |
| 7 |
Runtime error |
541 ms |
132096 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
469 ms |
107640 KB |
Output is correct |
| 2 |
Correct |
447 ms |
107592 KB |
Output is correct |
| 3 |
Correct |
468 ms |
92468 KB |
Output is correct |
| 4 |
Correct |
492 ms |
76512 KB |
Output is correct |
| 5 |
Correct |
497 ms |
118036 KB |
Output is correct |
| 6 |
Correct |
563 ms |
111836 KB |
Output is correct |
| 7 |
Correct |
1533 ms |
112816 KB |
Output is correct |
