#pragma GCC target("32")
#include<stdio.h>
#include<bitset>
#define next uwuwuwuwu
using namespace std;
using ll = long long;
const int maxn = 1e6 + 6;
const ll inf = (1ll<<50);
int n;
int up[maxn];
ll dp[maxn];
int tmp[maxn], tmp2[maxn], sz = 0, offset = 0, tsz = 0;
bitset<maxn> vis;
int link[maxn], next[maxn];
__attribute__(( always_inline)) inline void add_edge(int v, int ch) {
next[ch] = link[v];
link[v] = ch;
}
ll ans;
void dfs(int v) {
#define u link[v]
for(dp[v] = 0; u; u = next[u]) {
dfs(u);
ans = max(ans, dp[v] + dp[u] + up[u]);
dp[v] = max(dp[v], dp[u] + up[u]);
}
#undef u
}
int main() {
//cin.tie(0)->sync_with_stdio(0);
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d%lld", &up[i], &dp[i]);
}
for(int i = 1; i <= n; i++) if(!vis[i]) {
sz = offset;
int v = i;
while(!vis[v]) {
tmp[sz] = v;
tmp2[sz++] = dp[v];
vis[v] = 1;
v = up[v];
}
for(int i = 0; offset+i < sz-i-1; i++) {
swap(tmp[offset+i], tmp[sz-1-i]);
swap(tmp2[offset+i], tmp2[sz-1-i]);
}
while(sz>offset && tmp[sz-1] != v) sz--;
for(int i = offset+1; i < sz; i++)
swap(tmp2[i], tmp2[i-1]);
if(sz<=offset) continue;//no new cycle
tmp2[sz-1] *= -1;
offset = sz;
}
vis = 0;
for(int i = 0; i < sz; i++)
vis[tmp[i]] = 1;
for(int i = 1; i <= n; i++) if(!vis[i]) {
add_edge(up[i], i);
}
for(int i = 0; i <= n; i++)
up[i] = dp[i];
ll totalAns = 0, total = 0, pref = 0, A = -inf, B = -inf;
for(int start = 0, end = 0; start < sz; start = ++end) {
total = 0, pref = 0, A = -inf, B = -inf, ans = -inf;
while(tmp2[end] >= 0) {
total += tmp2[end];
end++;
}
for(int i = start; i <= end; i++) {
dfs(tmp[i]);
ans = max(ans, A + pref + dp[tmp[i]]);
ans = max(ans, B + dp[tmp[i]] + (total-pref) - tmp2[end]);
A = max(A, dp[tmp[i]]-pref);
B = max(B, dp[tmp[i]]+pref);
pref += tmp2[i];
}
totalAns += ans;
}
printf("%lld", totalAns);
}
Compilation message
islands.cpp:1:24: error: attribute(target("32")) is unknown
1 | #pragma GCC target("32")
| ^
islands.cpp: In function 'int main()':
islands.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
35 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
islands.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
37 | scanf("%d%lld", &up[i], &dp[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
