#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;
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]].fi, edg[cyc[i][0]].se, cyc[i][0]);
long long opt = 0;
long long total = 0;
for(int q = 0; q < cyc[i].size(); q++) {
int k = cyc[i][q];
total += c[k];
psum[q] = c[k];
if(q) psum[q] += psum[q-1];
}
for(int q=0; q<cyc[i].size(); q++) {
for(int r=0; r+1<cyc[i].size(); r++) {
int z = (q+r) % cyc[i].size();
int u = edg[cyc[i][q]].fi;
int v = edg[cyc[i][(q+r) % cyc[i].size()]].se;
if(u == v) continue;
opt = max(opt, trav(u) + trav(v) + max(sum(q,(q+r) % cyc[i].size(), i), total - sum(q,(q+r) % cyc[i].size(), i)));
}
}
// cout << " :: " << opt << endl;
ans += opt;
}
}
printf("%lld", ans);
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:101:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int q = 0; q < cyc[i].size(); q++) {
| ~~^~~~~~~~~~~~~~~
islands.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int q=0; q<cyc[i].size(); q++) {
| ~^~~~~~~~~~~~~~
islands.cpp:109:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int r=0; r+1<cyc[i].size(); r++) {
| ~~~^~~~~~~~~~~~~~
islands.cpp:110:25: warning: unused variable 'z' [-Wunused-variable]
110 | int z = (q+r) % cyc[i].size();
| ^
islands.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
islands.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%lld %lld", &j, &l);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
47188 KB |
Output is correct |
| 2 |
Incorrect |
27 ms |
47236 KB |
Output isn't correct |
| 3 |
Correct |
31 ms |
47312 KB |
Output is correct |
| 4 |
Correct |
26 ms |
47188 KB |
Output is correct |
| 5 |
Correct |
25 ms |
47220 KB |
Output is correct |
| 6 |
Correct |
27 ms |
47180 KB |
Output is correct |
| 7 |
Correct |
24 ms |
47308 KB |
Output is correct |
| 8 |
Correct |
26 ms |
47188 KB |
Output is correct |
| 9 |
Correct |
27 ms |
47260 KB |
Output is correct |
| 10 |
Incorrect |
28 ms |
47232 KB |
Output isn't correct |
| 11 |
Correct |
27 ms |
47236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
47312 KB |
Output is correct |
| 2 |
Correct |
27 ms |
47412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
47444 KB |
Output is correct |
| 2 |
Correct |
157 ms |
47816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
346 ms |
48636 KB |
Output is correct |
| 2 |
Execution timed out |
2090 ms |
51652 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2086 ms |
53420 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2090 ms |
64952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2085 ms |
74940 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
374 ms |
130316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
454 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
