Submission #1170359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170359		Dan4Life	Islands (IOI08_islands)	C++20	80 / 100	543 ms	129728 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<int,2>;
using ar3 = array<int,3>;
using vi = vector<int>;
const int mxN = (int)1e6+1;

vi w;
ar2 nx[mxN];
ll n, far, SS;
bitset<mxN> cyc, vis;
ar3 adj[mxN*2];
int adjH[mxN];
ll dis[mxN];
int allowed_S;
vi xd;

ar2 dfs2(int s){
	ar2 ans = {0,s}; vis[s] = 1; xd.pb(s);
	for(int x = adjH[s]; x; x=adj[x][1]){
		int u = adj[x][0]; ll w = adj[x][2];
		if(vis[u]) continue;
		auto [xx,y] = dfs2(u);
		ans = max(ans, {xx+w,y});
	}
	return ans;
}

void dfs(int s, int p){
	dis[s] = 0;
	for(int x = adjH[s]; x; x=adj[x][1]){
		int u = adj[x][0], w = adj[x][2];
		if(u==p or cyc[u]) continue;
		dfs(u,s); dis[s] = max(dis[s], dis[u]+w);
	}
}

ll compute_diam(int s){
	allowed_S = s; xd.clear();
	int a = dfs2(s)[1]; 
	for(auto u : xd) vis[u]=0; xd.clear();
	return dfs2(a)[0];
}

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}; 
		adj[i*2-1] = {i,adjH[x],w}; adjH[x]=i*2-1;
		adj[i*2] = {x,adjH[i],w}; adjH[i]=i*2;
	}
	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];
		ll sum = 0;
		for(auto u : v) sum = max(sum, compute_diam(u)), dfs(u,0);
		int m = sz(v); for(int i = 0; i < m; i++) v.pb(v[i]);
		vector<ll> pref(m+1,0);
		multiset<ll> S; S.clear(); 
		for(int i = 0; i < m; i++){
			sum=max(sum,dis[v[i]]);
			pref[i+1]=pref[i]+(ll)nx[v[i]][1];
			S.insert(dis[v[i]]-pref[i]);	
		}
		if(sz(v)>2){
			for(int i = m; i < sz(v); i++){
				S.erase(S.find(dis[v[i-m]]-pref[i-m]));
				sum=max(sum, dis[v[i]]+pref[m]+pref[i-m]+*prev(end(S))); 
				S.insert(dis[v[i]]-(pref[m]+pref[i-m]));
			}
		}
		ans+=sum;
	}
	cout << ans << "\n";
}

Compilation message (stderr)

islands.cpp: In function 'ar2 dfs2(int)':
islands.cpp:27:35: warning: narrowing conversion of '(((ll)xx) + w)' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   27 |                 ans = max(ans, {xx+w,y});
      |                                 ~~^~

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