#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<pair<int,int> > adj[1000005];
int trip[1000005], w[1000005];
bool chk[1000005];
vector<int> cycle,len;
ll dd[1000005], a[2000005];
vector<ll> d;
int vn;
int dfs(int now, int pi) {
int ret = trip[now] = ++vn;
for (auto &e : adj[now]) {
if (e.second==pi)continue;
if (!trip[e.first]) {
ret=min(ret,dfs(e.first, e.second));
}
else if(!chk[e.first]){
ret = min(ret, trip[e.first]);
cycle.push_back(e.first);
chk[e.first] = true;
len.push_back(w[e.second]);
}
}
if (ret < trip[now]) {
chk[now] = true;
cycle.push_back(now);
len.push_back(w[pi]);
}
}
ll val;
void dfs2(int now) {
chk[now] = true;
for (auto &e : adj[now]) {
if (chk[e.first])continue;
dfs2(e.first);
val = max(val, dd[now] + dd[e.first] + w[e.second]);
dd[now] = max(dd[now], dd[e.first] + w[e.second]);
}
}
ll calc(vector<ll> &d, vector<int> &len, int m) {
deque<int> dq;
ll sum = len[0];
for (int i = 1; i < m * 2; i++) {
a[i] = sum + d[i%m];
sum += len[i%m];
}
ll ret = 0;
sum = 0;
int ri;
ri = 0;
for (int i = 0; i < m; i++) {
for (int j = ri; j < i + m; j++) {
while (!dq.empty() && a[dq.back()] <= a[j])dq.pop_back();
dq.push_back(j);
}
ri = i + m;
while (!dq.empty() && dq.front() <= i)dq.pop_front();
ll temp = d[i] + a[dq.front()] - sum;
ret = max(ret, temp);
sum += len[i];
}
return ret;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int a, b;
scanf("%d%d", &a, &b);
adj[i].emplace_back(a,i);
adj[a].emplace_back(i,i);
w[i] = b;
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
if (!trip[i]) {
cycle.clear();
len.clear();
dfs(i, 0);
int m = cycle.size();
d = vector<ll>(m);
val = 0;
for (int i = 0; i < cycle.size(); i++) {
dfs2(cycle[i]);
d[i] = dd[cycle[i]];
}
val = max(val,calc(d, len, m));
reverse(len.begin(), len.end() - 1);
reverse(d.begin(), d.end());
val = max(val, calc(d, len, m));
ans += val;
}
}
printf("%lld\n", ans);
return 0;
}
Compilation message
islands.cpp: In function 'int dfs(int, int)':
islands.cpp:31:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
islands.cpp: In function 'int main()':
islands.cpp:84:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < cycle.size(); i++) {
~~^~~~~~~~~~~~~~
islands.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
islands.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
23764 KB |
Output isn't correct |
| 2 |
Incorrect |
25 ms |
23936 KB |
Output isn't correct |
| 3 |
Incorrect |
21 ms |
23976 KB |
Output isn't correct |
| 4 |
Incorrect |
21 ms |
24040 KB |
Output isn't correct |
| 5 |
Incorrect |
21 ms |
24040 KB |
Output isn't correct |
| 6 |
Incorrect |
25 ms |
24040 KB |
Output isn't correct |
| 7 |
Incorrect |
23 ms |
24040 KB |
Output isn't correct |
| 8 |
Incorrect |
21 ms |
24040 KB |
Output isn't correct |
| 9 |
Incorrect |
21 ms |
24040 KB |
Output isn't correct |
| 10 |
Incorrect |
22 ms |
24040 KB |
Output isn't correct |
| 11 |
Incorrect |
22 ms |
24088 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
24136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
24136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
25040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
303 ms |
37832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
209 ms |
46344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
458 ms |
72116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
559 ms |
133648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
