Submission #1036141

#TimeUsernameProblemLanguageResultExecution timeMemory
1036141thinknoexitIslands (IOI08_islands)C++17
100 / 100
682 ms116320 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1000001; vector<pair<int, int>> adj[N]; int deg[N], lv[N]; bool cycle[N], vis[N]; ll dp[2][N], qs[N], a[N]; ll res = 0; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n; cin >> n; for (int i = 1;i <= n;i++) { int a, x; cin >> a >> x; adj[i].push_back({ a, x }); adj[a].push_back({ i, x }); deg[i]++, deg[a]++; } // find cycle using kahn's algorithm { queue<int> q; for (int i = 1;i <= n;i++) { cycle[i] = 1; if (deg[i] == 1) q.push(i); } while (!q.empty()) { int v = q.front(); q.pop(); cycle[v] = 0; vis[v] = 1; for (auto& x : adj[v]) { if (!vis[x.first]) { lv[x.first] = max(lv[x.first], lv[v] + 1); } if (--deg[x.first] == 1) q.push(x.first); } } memset(vis, 0, sizeof vis); } //for (int i = 1;i <= n;i++) cout << lv[i] << ' '; ll ans = 0; // for each component find the longest path and sum up to answer for (int i = 1;i <= n;i++) { if (!cycle[i] || vis[i]) continue; vector<pair<int, int>> c; c.push_back({ 0, 0 }); int now = i, p = -1; while (1) { bool ch = 0; vis[now] = 1; for (auto& x : adj[now]) { if (!cycle[x.first] || x.first == p) continue; c.push_back({ now, x.second }); if (!vis[x.first]) { p = now; ch = 1; now = x.first; break; } } if (!ch) { if ((int)c.size() == 2) { // parallel edge multiset<int> s; for (auto& x : adj[now]) { if (!cycle[x.first]) continue; s.insert(x.second); } s.erase(s.find(c.back().second)); c.push_back({ now, *s.begin() }); } break; } } res = 0; // c is list of cycle in order { // dp on tree for (auto& x : c) vis[x.first] = 0; // bfs vector<int> nodes; queue<int> q; q.push(i), vis[i] = 1; while (!q.empty()) { int v = q.front(); q.pop(); nodes.push_back(v); for (auto& x : adj[v]) if (!vis[x.first]) q.push(x.first), vis[x.first] = 1; } sort(nodes.begin(), nodes.end(), [&](int a, int b) { return lv[a] < lv[b]; }); for (auto& v : nodes) { dp[0][v] = dp[1][v] = 0; for (auto& x : adj[v]) { if (lv[v] < lv[x.first] || cycle[x.first]) continue; dp[1][v] = max(dp[1][v], dp[0][x.first] + x.second); if (dp[1][v] > dp[0][v]) swap(dp[0][v], dp[1][v]); } res = max(res, dp[0][v] + dp[1][v]); } } int sz = c.size() - 1; for (int i = 1;i <= sz;i++) { qs[i] = qs[i - 1] + c[i - 1].second; a[i] = dp[0][c[i].first]; } ll mx = -1e18, mx2 = -1e18; ll sk = c[sz].second; for (int i = 1;i <= sz;i++) { res = max(res, mx + qs[i] + a[i]); res = max(res, mx2 + qs[sz] - qs[i] + a[i] + sk); mx = max(mx, -qs[i] + a[i]); mx2 = max(mx2, qs[i] + a[i]); } ans += res; //cout << res << ' '; } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...