#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
const int nax = 1e6;
int n;
int cnt = 1;
int vis[nax+5];
int c[nax+5]; //cost
long long val[nax+5];
vector<pii> adj[nax+5];
vector<pii> edg;
vector<int> cyc;
void gp(int u, int ls=0) {
// cout << "visiting " << u << endl;
vis[u]=cnt;
for (auto t : adj[u]) {
int v = t.fi;
int e = t.se;
//cout << u << " " << v << " " << e << " " << ls << endl;
if(e==ls) continue;
if(vis[v] != cnt) gp(v, e);
else {
//cout << "edge " << u << " " << v << endl;
cyc.push_back(e);
}
}
}
bool fc(int u, int go, int ls) {
if(u == go) return true;
for(auto 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] = cnt;
vis[v] = cnt;
//cout << u << " " << v << endl;
if(edg[e].fi == u) swap(edg[e].fi, edg[e].se);
cyc.push_back(e);
return true;
}
}
return false;
}
long long nono = 0;
long long trav(int u) {
if(val[u] != -1) return val[u];
vis[u] = cnt;
priority_queue<long long, vector<long long>, greater<long long>> pq;
for(pii t : adj[u]) {
int v = t.fi;
int e = t.se;
if(vis[v] != cnt) {
pq.push(1ll*c[e] + trav(v));
}
while(pq.size() > 2) pq.pop();
}
if(pq.size() == 2) {
long long tmp = pq.top();
pq.pop();
nono = max(nono, tmp + pq.top());
}
return val[u] = pq.empty() ? 0 : pq.top();
}
signed 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;
val[i] = -1;
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(!vis[i]) {
cnt++;
nono = 0;
cyc.clear();
gp(i);
cyc.pop_back();
cnt++;
fc(edg[cyc[0]].se, edg[cyc[0]].fi, cyc[0]);
swap(edg[cyc[0]].fi, edg[cyc[0]].se);
int m = cyc.size();
for(int j=0; j<m; j++) {
val[edg[cyc[j]].fi] = trav(edg[cyc[j]].fi);
if(edg[cyc[j]].fi != edg[cyc[(j-1+m) % m]].se) swap(edg[cyc[j]].fi, edg[cyc[j]].se);
}
long long opt = 0;
deque<pair<long long, int>> dq;
long long dif = 0;
long long sum = 0;
int cnt = 0;
for(int j=0; j<m; j++) {
int e = cyc[j];
sum += 1ll*c[e];
if(j+1 < m) {
long long temp = sum + trav(edg[e].se);
while(!dq.empty() && dq.back().fi <= temp) dq.pop_back();
dq.push_back({temp, cnt++});
}
}
for(int j=0; j<m; j++) {
int e = cyc[j];
int u = edg[e].fi;
opt = max(opt , trav(u) + dq.front().fi + dif);
dif -= 1ll*c[e];
long long temp = trav(u) + sum - 1ll*c[e] - dif;
while(!dq.empty() && dq.front().se <= cnt-m) dq.pop_front();
while(!dq.empty() && dq.back().fi <= temp) dq.pop_back();
dq.push_back({temp, cnt++});
}
ans += max(opt,nono);
}
}
printf("%lld", ans);
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
islands.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | scanf("%lld %lld", &j, &l);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
23836 KB |
Output isn't correct |
| 3 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 4 |
Correct |
12 ms |
23728 KB |
Output is correct |
| 5 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 6 |
Correct |
13 ms |
23704 KB |
Output is correct |
| 7 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 8 |
Correct |
12 ms |
23780 KB |
Output is correct |
| 9 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 10 |
Correct |
12 ms |
23716 KB |
Output is correct |
| 11 |
Correct |
12 ms |
23764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23892 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23864 KB |
Output is correct |
| 2 |
Correct |
15 ms |
24248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
24916 KB |
Output is correct |
| 2 |
Correct |
34 ms |
27836 KB |
Output is correct |
| 3 |
Correct |
23 ms |
25344 KB |
Output is correct |
| 4 |
Incorrect |
17 ms |
24532 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
28884 KB |
Output is correct |
| 2 |
Correct |
49 ms |
32796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
37876 KB |
Output is correct |
| 2 |
Correct |
125 ms |
46584 KB |
Output is correct |
| 3 |
Correct |
128 ms |
58444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
156 ms |
49004 KB |
Output is correct |
| 2 |
Correct |
253 ms |
75008 KB |
Output is correct |
| 3 |
Correct |
243 ms |
88684 KB |
Output is correct |
| 4 |
Correct |
295 ms |
112060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
345 ms |
101840 KB |
Output is correct |
| 2 |
Runtime error |
566 ms |
131072 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
370 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
