/* it could have been better :) it will next time ;) */ #include <bits/stdc++.h> using namespace std; #define ll long long #define INF 1e18 #define f first #define s second #define pii pair<int, int> #define vi vector<int> const int MOD = 1'000'000'000 + 7; void setIO(string name = "") { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); #ifdef LOCAL freopen("inp.txt", "r", stdin); freopen("out.txt", "w", stdout); #else if (!name.empty()) { freopen((name + ".INP").c_str(), "r", stdin); freopen((name + ".OUT").c_str(), "w", stdout); } #endif } const int MAXN = 1e6; int n; vector<tuple<int, int, int>> g[MAXN + 5]; ll dfs_diameter(int u, int p_edge_id, pii skip, ll &mx, ll &mx2) { ll a0 = -INF, a1 = -INF; for(auto [v, w, id] : g[u]) { if(id == p_edge_id || v == skip.f || v == skip.s) continue; ll cur = dfs_diameter(v, id, skip, mx, mx2) + w; if(cur >= a0) { a1 = a0; a0 = cur; } else if(cur > a1) { a1 = cur; } } pair<ll, ll> cur = {0, 0}; if(a0 != -INF) cur.f = cur.s = a0; if(a1 != -INF) cur.s += a1; mx = max(mx, cur.f); mx2 = max(mx2, cur.s); return cur.f; } bool vis[MAXN + 5]; pii par[MAXN + 5]; bool found_cycle = true; int st = -1, en = -1; int cycle_w = -1; void dfs_cycle(int u, int p_edge_id = -1) { if(p_edge_id == -1) { found_cycle = false; st = -1, en = -1; cycle_w = -1; } vis[u] = true; for(auto [v, w, id] : g[u]) { if(id == p_edge_id) continue; if(vis[v]) { if(!found_cycle) { st = u, en = v; found_cycle = true; cycle_w = w; } } else { par[v] = {u, w}; dfs_cycle(v, id); } } } vector<pii> find_cycle() { if(st == -1) return {}; vector<pii> cycle; int cur = st; while(cur != en && cur != 0) { cycle.push_back({cur, par[cur].second}); cur = par[cur].first; } if(cur == 0) return {}; cycle.push_back({en, cycle_w}); reverse(cycle.begin(), cycle.end()); return cycle; } ll f[MAXN + 5]; void solve() { cin >> n; for(int i = 1; i <= n; i++) { int j; cin >> j; int w; cin >> w; g[i].push_back({j, w, i}); g[j].push_back({i, w, i}); } ll res = 0; for(int i = 1; i <= n; i++) { if(vis[i]) continue; dfs_cycle(i); vector<pii> cycle = find_cycle(); ll cur = 0; int m = cycle.size(); for(int i = 0; i < m; i++) { cycle.push_back(cycle[i]); dfs_diameter(cycle[i].f, -1, {cycle[(i - 1 + m) % m].f, cycle[(i + 1) % m].f}, f[cycle[i].f], cur); } vector<ll> ps(m * 2); for(int i = 1; i < m * 2; i++) ps[i] = ps[i - 1] + cycle[i].s; deque<pii> dq; dq.push_back({f[cycle[0].f], 0}); for(int i = 1; i < m * 2; i++) { while(!dq.empty() && dq.front().s + m <= i) dq.pop_front(); cur = max(cur, f[cycle[i].f] + ps[i] + dq.front().f); while(!dq.empty() && dq.back().f <= f[cycle[i].f] - ps[i]) dq.pop_back(); dq.push_back({f[cycle[i].f] - ps[i], i}); } res += cur; } cout << res << '\n'; } signed main() { setIO(); int t = 1; // cin >> t; while (t--) solve(); }

islands.cpp: In function 'void setIO(std::string)':
islands.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen((name + ".INP").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name + ".OUT").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~