#include "bits/stdc++.h"
using namespace std;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
const int nax = 1e6;
int n;
int p[nax+5];
bool vis[nax+5];
long long c[nax+5];
long long val[nax+5];
long long psum[nax+5];
vector<pii> adj[nax+5];
vector<int> cyc[nax+5];
vector<pii> edg;
void gp(int u, int par, int ls=0) {
p[u] = par;
for(pii t : adj[u]) {
int v = t.fi;
int e = t.se;
if(e == ls) continue;
if(p[v] == 0) {
gp(v, par, e);
} else {
cyc[par].push_back(e);
}
}
}
bool fc(int u, int go, int ls) {
if(u == go) return true;
for(pii t : adj[u]) {
int v = t.fi;
int e = t.se;
if(e == ls) continue;
bool ok = fc(v, go, e);
if(ok) {
vis[u] = true;
vis[v] = true;
if(edg[e].fi != u) swap(edg[e].fi, edg[e].se);
cyc[p[go]].push_back(e);
return true;
}
}
return false;
}
long long trav(int u) {
if(val[u]) return val[u];
vis[u] = true;
long long res = 0;
for(pii t : adj[u]) {
int v = t.fi;
int e = t.se;
if(!vis[v]) {
res = max(res, c[e] + trav(v));
}
}
return val[u] = res;
}
long long sum (int l, int r, int i) {
if(r < l) return psum[r] + psum[cyc[i].size()-1] - psum[l-1];
if(l) return psum[r] - psum[l-1];
return psum[r];
}
int main () {
scanf("%d", &n);
edg.pb({0,0});
for(int i=1; i<=n; i++) {
long long l, j;
scanf("%lld %lld", &j, &l);
c[i] = l;
adj[j].pb({i,i});
adj[i].pb({j,i});
edg.pb({i,j});
}
long long ans = 0;
for(int i=1; i<=n; i++) {
if(p[i] == 0) {
gp(i,i);
cyc[i].pop_back();
fc(edg[cyc[i][0]].se, edg[cyc[i][0]].fi, cyc[i][0]);
long long opt = 0;
priority_queue<long long> pq;
long long dpq = 0;
long long sum = 0;
int sz = cyc[i].size();
for(int j=0; j<sz; j++) {
int e = cyc[i][j];
swap(edg[e].fi, edg[e].se);
sum += c[e];
if(j+1 < sz) pq.push(sum + trav(edg[e].se));
}
for(int j=0; j<sz; j++) {
int e = cyc[i][j];
int u = edg[e].fi;
opt = max(opt, trav(u) + pq.top() + dpq);
dpq -= c[e];
pq.push(trav(u) + sum - c[e] - dpq);
}
sum = 0;
dpq = 0;
while(!pq.empty()) pq.pop();
for(int j=sz-1; j>=0; j--) {
int e = cyc[i][j];
sum += c[e];
if(j > 0) pq.push(sum + trav(edg[e].fi));
}
for(int j=sz-1; j>=0; j--) {
int e = cyc[i][j];
int u = edg[e].se;
opt = max(opt, trav(u) + pq.top() + dpq);
dpq -= c[e];
pq.push(trav(u) + sum - c[e] - dpq);
}
ans += opt;
}
}
printf("%lld", ans);
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
islands.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%lld %lld", &j, &l);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
47316 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
47268 KB |
Output isn't correct |
| 3 |
Correct |
29 ms |
47316 KB |
Output is correct |
| 4 |
Correct |
26 ms |
47292 KB |
Output is correct |
| 5 |
Correct |
29 ms |
47264 KB |
Output is correct |
| 6 |
Correct |
31 ms |
47252 KB |
Output is correct |
| 7 |
Correct |
24 ms |
47188 KB |
Output is correct |
| 8 |
Correct |
23 ms |
47232 KB |
Output is correct |
| 9 |
Correct |
27 ms |
47220 KB |
Output is correct |
| 10 |
Incorrect |
24 ms |
47316 KB |
Output isn't correct |
| 11 |
Correct |
24 ms |
47284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
47316 KB |
Output is correct |
| 2 |
Correct |
25 ms |
47400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
47404 KB |
Output is correct |
| 2 |
Correct |
30 ms |
47908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
48768 KB |
Output is correct |
| 2 |
Correct |
48 ms |
51908 KB |
Output is correct |
| 3 |
Correct |
35 ms |
48948 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
48048 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
53816 KB |
Output is correct |
| 2 |
Correct |
89 ms |
56948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
63656 KB |
Output is correct |
| 2 |
Correct |
161 ms |
72660 KB |
Output is correct |
| 3 |
Correct |
183 ms |
88248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
273 ms |
76252 KB |
Output is correct |
| 2 |
Correct |
282 ms |
112892 KB |
Output is correct |
| 3 |
Correct |
402 ms |
123360 KB |
Output is correct |
| 4 |
Runtime error |
314 ms |
131072 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
359 ms |
115500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
352 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
