| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1162558 | Dan4Life | Islands (IOI08_islands) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
using ll = long long;
using ar2 = array<int,2>;
using vi = vector<int>;
const int mxN = (int)1e6+10;
ll n, far;
ar2 nx[mxN];
bitset<mxN> cyc;
vector<ar2> radj[mxN];
ll vis[mxN], pref[mxN];
void dfs(vector<ar2> adj[], int s, int p){
far=max(far,vis[s]);
for(auto [u,w] : adj[s]){
if(u==p or cyc[u]) continue;
vis[u] = vis[s]+w; dfs(adj,u,s);
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n; ll ans = 0;
for(int i = 1; i <= n; i++){
int x, w; cin >> x >> w;
nx[i]={x,w}; radj[x].pb({i,w});
}
for(int i = 1; i <= n; i++){
if(vis[i]) continue;
int x = i; vi v; v.clear();
while(!vis[x]) vis[x]=1,v.pb(x),x=nx[x][0];
for(auto u : v) vis[u]=0; v.clear();
while(!cyc[x]) cyc[x]=1,v.pb(x),x=nx[x][0];
for(auto u : v){ far = 0; dfs(radj,u,0); vis[u] = far; }
int m = sz(v); for(int i = 0; i < m; i++) v.pb(v[i]);
multiset<ll> S; S.clear(); ll sum = 0; pref[0] = 0;
for(int i = 0; i < sz(v); i++){
sum=max(sum,vis[v[i]]);
pref[i+1]=pref[i]+(ll)nx[v[i]][1];
if(i<m) S.insert(vis[v[i]]-pref[i]);
}
if(sz(v)>2){
for(int i = m; i < sz(v); i++){
S.erase(S.find(vis[v[i-m]]-pref[i-m]));
sum=max(sum, vis[v[i]]+pref[i]+*prev(end(S)));
S.insert(vis[v[i]]-pref[i]);
}
}
ans+=sum; for(auto u : v) vis[u]=1;
}
cout << ans << "\n";
}
--o---O