Submission #1162538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162538		Dan4Life	Islands (IOI08_islands)	C++20	64 / 100	292 ms	149112 KiB

islands

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
using ll = long long;
using ar2 = array<ll,2>;
using vi = vector<ll>;
const int mxN = (int)1e6+10;
ll n, far;
ar2 nx[mxN];
ll vis[mxN], cyc[mxN];
vector<ar2> radj[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(!vis[x]) vis[x]=cyc[x]=1,v.pb(x),x=nx[x][0];
		for(auto u : v){
			far = vis[u] = 0;
			dfs(radj,u,0); vis[u] = far;
		}
		multiset<ll> S, S2; S.clear(); S2.clear();
		ll sum = vis[v[0]], s = 0, tot = 0;
		for(int i = 0; i < sz(v); i++){
			ll w = nx[v[i]][1];
			s+=w; if(i<sz(v)-1) S.insert(vis[v[i+1]]+s);
			tot+=w;
		}
		s = 0;
		for(int i = 0; i < sz(v); i++){
			ll w = nx[v[i]][1];
			if(i) S.erase(S.find(vis[v[i]]+s));
			if(sz(S)) sum=max(sum, vis[v[i]]+*prev(end(S))-s); 
			if(sz(S2)) sum=max(sum, vis[v[i]]+tot-s+*prev(end(S2)));
			S2.insert(s+vis[v[i]]); s+=w;
		}
		for(auto u : v) vis[u]=1;
		ans+=sum;
	}
	cout << ans << "\n";
}

• Subtask 1: 27 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10