/* it could have been better :) it will next time ;) */ #include <bits/stdc++.h> using namespace std; #define int 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 } // START OF DEBUG #define db(val) "["#val" = "<<(val)<<"] " #define print_op(...) ostream& operator<<(ostream& out, const __VA_ARGS__& u) template<class U, class V> print_op(pair<U, V>) { return out << "(" << u.first << ", " << u.second << ")"; } template<class Con, class = decltype(begin(declval<Con>()))> typename enable_if<!is_same<Con, string>::value, ostream&>::type operator<<(ostream& out, const Con& con) { out << "{"; for (auto beg = con.begin(), it = beg; it != con.end(); ++it) out << (it == beg ? "" : ", ") << *it; return out << "}"; } template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); } template<class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); } // END OF DEBUG const int MAXN = 2e6; int n; vector<tuple<int, int, int>> g[MAXN + 5]; int dfs_diameter(int u, int p_edge_id, pii skip, int &mx, int &mx2) { vi a; for(auto [v, w, id] : g[u]) { if(id == p_edge_id || v == skip.f || v == skip.s) continue; a.push_back(dfs_diameter(v, id, skip, mx, mx2) + w); } sort(a.rbegin(), a.rend()); pii cur = {0, 0}; if(a.size() > 0) cur.f = cur.s = a[0]; if(a.size() > 1) cur.s += a[1]; 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; } int 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}); } int res = 0; for(int i = 1; i <= n; i++) { if(vis[i]) continue; dfs_cycle(i); vector<pii> cycle = find_cycle(); int 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); } // m = cycle.size(); vi ps(m * 2); for(int i = 1; i < m * 2; i++) ps[i] = ps[i - 1] + cycle[i].s; multiset<int> ms; ms.insert(f[cycle[0].f]); // cycle[0].s = 0; for(int i = 1; i < m * 2; i++) { cur = max(cur, f[cycle[i].f] + ps[i] - *ms.rbegin()); ms.insert(f[cycle[i].f] - ps[i] + cycle[i].s); if(i >= m) { auto it = ms.find((f[cycle[i - m].f] - ps[i - m] + cycle[i - m].s)); if(it != ms.end()) ms.erase(it); } } res += cur; // cout << cycle << '\n'; } 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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~