제출 #885668

#제출 시각아이디문제언어결과실행 시간메모리
885668TobIslands (IOI08_islands)C++14
34 / 100
154 ms63712 KiB
#include <bits/stdc++.h> #define ll long long #define F first #define S second #define all(x) x.begin(), x.end() #define pb push_back #define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) using namespace std; typedef pair <int, int> pii; typedef pair <ll, ll> pll; const ll N = 1e6 + 7, inf = 1e18; ll n, ro, sp, res; int a[N], b[N], bio[N], cyc[N], deg[N]; ll dp[N], dis[N], rdis[N], pr[N], pr2[N], suf[N], suf2[N]; pll cur[N]; queue <int> q; void Merge(pll& x, ll y) { if (y >= x.F) x = {y, x.F}; else x = {x.F, max(x.S, y)}; } void dfs() { int x = q.front(); q.pop(); pii y = {a[x], b[x]}; res = max(res, cur[x].F + cur[x].S); dp[x] = cur[x].F; Merge(cur[y.F], dp[x] + y.S); if (cyc[y.F]) return; deg[y.F]--; if (!deg[y.F]) q.push(y.F); } int main () { FIO; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; deg[a[i]]++; } for (int i = 1; i <= n; i++) { if (bio[i]) continue; int x = a[i], y = i; bio[i] = i; while (!bio[x]) { bio[x] = i; y = x; x = a[x]; } if (bio[x] == i) { cyc[y] = 1; while (x != y) { cyc[x] = 1; x = a[x]; } } } memset(bio, 0, sizeof bio); for (int i = 1; i <= n; i++) if (!deg[i]) q.push(i); while (!q.empty()) dfs(); ll sum = 0; for (int i = 1; i <= n; i++) { if (bio[i]) continue; int x = a[i], y = i; bio[i] = i; while (!bio[x]) { bio[x] = i; y = x; x = a[x]; } if (bio[x] == i) { res = 0; vector <int> v; v = {0, y}; while (x != y) { v.pb(x); x = a[x]; } int siz = v.size(); pr[0] = pr2[0] = suf[siz] = suf2[siz] = -inf; for (int i = siz-1; i; i--) rdis[i] = rdis[i+1] + (i < siz-1)*b[v[i]]; for (int i = 1; i < siz; i++) { dis[i] = dis[i-1] + b[v[i-1]]; dp[v[i]] = cur[v[i]].F; pr[i] = max(pr[i-1], dp[v[i]] + dis[i]); pr2[i] = max(pr2[i-1], dp[v[i]] + rdis[i]); } for (int i = siz-1; i; i--) { suf[i] = max(suf[i+1], dp[v[i]] + dis[i]); suf2[i] = max(suf2[i+1], dp[v[i]] + rdis[i]); } for (int i = 1; i < siz; i++) { // cout << i << "i " << v[i] << "x " << dis[i] << "d " << rdis[i] << "rd " << pr[i] << "p " << pr2[i] << "pp " << suf[i] << "s " << suf2[i] << "ss " << dp[v[i]] << "dp\n"; res = max(res, dp[v[i]] + max(suf[i+1] - dis[i], pr[i-1] + rdis[i] + b[v.back()])); res = max(res, dp[v[i]] + max(pr2[i-1] - rdis[i], suf2[i+1] + dis[i] + b[v.back()])); } sum += res; } } cout << sum; 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...