#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000100;
int n;
int ar[MAXN], wg[MAXN], in[MAXN], pai[MAXN];
int op[MAXN];
long long prof[MAXN], sc[MAXN], dist[MAXN];
bool marc[MAXN], isCycle[MAXN];
long long ans;
vector<int> rev[MAXN], rwg[MAXN];
int dfs1(int cur);
long long dfs2(int cur);
void getCycle();
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d %d", &ar[i], &wg[i]);
rev[ar[i]].push_back(i);
rev[i].push_back(ar[i]);
rwg[ar[i]].push_back(wg[i]);
rwg[i].push_back(wg[i]);
in[ar[i]]++;
}
getCycle();
printf("%lld\n", ans);
}
int dfs1(int cur){
// printf("\t\t%d\n", cur);
marc[cur] = 1;
int ret = cur;
for(int i = 0; i < rev[cur].size(); i++){
int viz = rev[cur][i];
if(in[viz]) continue;
if(marc[viz]) continue;
pai[viz] = pai[cur];
dist[viz] = dist[cur] + rwg[cur][i];
int aux = dfs1(viz);
if(dist[aux] > dist[ret]) ret = aux;
}
return ret;
}
long long dfs2(int cur){
marc[cur] = 0;
long long ret = dist[cur];
for(int i = 0; i < rev[cur].size(); i++){
int viz = rev[cur][i];
if(isCycle[viz] && pai[cur] != viz) continue;
if(!marc[viz]) continue;
dist[viz] = dist[cur] + rwg[cur][i];
ret = max(ret, dfs2(viz));
}
return ret;
}
void getCycle(){
queue<int> fila;
for(int i = 1; i <= n; i++)
if(in[i] == 0) fila.push(i);
while(!fila.empty()){
int cur = fila.front();
fila.pop();
int viz = ar[cur];
in[viz]--;
prof[viz] = max(prof[viz], prof[cur] + wg[cur]);
if(in[viz] == 0) fila.push(viz);
}
for(int i = 1; i <= n; i++){
if(in[i] == 0 || isCycle[i]) continue;
// printf("New Cycle %d\n", i);
int cur = i;
sc[cur] = 0;
long long aux = 0;
long long sct = 0;
while(1) {
// printf("\tCur: %d\n", cur);
isCycle[cur] = 1;
pai[cur] = cur;
dist[cur] = 0;
int x = dfs1(cur);
dist[x] = 0;
long long y = dfs2(x);
aux = max(aux, y);
// printf("\t\tMaxDist = %lld\n", y);
sct += wg[cur];
op[ar[cur]] = cur;
if(ar[cur] == i) break;
sc[ar[cur]] = sc[cur] + wg[cur];
cur = ar[cur];
}
// printf("\t%lld %lld\n", aux, sct);
cur = ar[i];
long long aux2 = prof[i] - sc[i];
long long aux3 = prof[i] + sc[i];
while(1){
if(cur == i) break;
aux = max(aux, aux2 + prof[cur] + sc[cur]);
aux = max(aux, aux3 + sct + prof[cur] - sc[cur]);
// printf("\t\taux = max(aux, %lld, %lld)\n", aux2 + prof[cur] + sc[cur], sct + prof[cur] - sc[cur]);
aux2 = max(aux2, prof[cur] - sc[cur]);
aux3 = max(aux3, prof[cur] + sc[cur]);
cur = ar[cur];
}
// printf("\t%lld\n", aux);
cur = op[op[i]];
aux2 = prof[ar[cur]] + sc[ar[cur]];
aux3 = prof[ar[cur]] - sc[ar[cur]];
while(1){
if(cur == op[i]) break;
aux = max(aux, aux2 + prof[cur] - sc[cur]);
aux = max(aux, aux3 + sct + prof[cur] + sc[cur]);
// printf("\t\taux = max(aux, %lld, %lld)\n", aux2 + prof[cur] - sc[cur], sct + prof[cur] + sc[cur]);
aux2 = max(aux2, prof[cur] + sc[cur]);
aux3 = max(aux3, prof[cur] - sc[cur]);
cur = op[cur];
}
// printf("\t%lld\n\n", aux);
ans += aux;
}
}
Compilation message
islands.cpp: In function 'int dfs1(int)':
islands.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < rev[cur].size(); i++){
~~^~~~~~~~~~~~~~~~~
islands.cpp: In function 'long long int dfs2(int)':
islands.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < rev[cur].size(); i++){
~~^~~~~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
islands.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &ar[i], &wg[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
47360 KB |
Output is correct |
2 |
Correct |
32 ms |
47360 KB |
Output is correct |
3 |
Correct |
37 ms |
47352 KB |
Output is correct |
4 |
Correct |
32 ms |
47360 KB |
Output is correct |
5 |
Correct |
33 ms |
47360 KB |
Output is correct |
6 |
Correct |
33 ms |
47352 KB |
Output is correct |
7 |
Correct |
33 ms |
47352 KB |
Output is correct |
8 |
Correct |
33 ms |
47360 KB |
Output is correct |
9 |
Correct |
33 ms |
47360 KB |
Output is correct |
10 |
Correct |
32 ms |
47360 KB |
Output is correct |
11 |
Correct |
32 ms |
47360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
47480 KB |
Output is correct |
2 |
Correct |
34 ms |
47480 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
47612 KB |
Output is correct |
2 |
Correct |
37 ms |
47872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
44 ms |
49272 KB |
Output is correct |
2 |
Correct |
58 ms |
51576 KB |
Output is correct |
3 |
Correct |
50 ms |
50040 KB |
Output is correct |
4 |
Correct |
41 ms |
48632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
53496 KB |
Output is correct |
2 |
Correct |
95 ms |
59416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
162 ms |
72180 KB |
Output is correct |
2 |
Correct |
159 ms |
72312 KB |
Output is correct |
3 |
Correct |
204 ms |
78328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
264 ms |
95864 KB |
Output is correct |
2 |
Correct |
327 ms |
108024 KB |
Output is correct |
3 |
Correct |
343 ms |
112760 KB |
Output is correct |
4 |
Correct |
418 ms |
126200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
477 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
587 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |