Submission #1171848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171848		rayan_bd	Cyberland (APIO23_cyberland)	C++20	0 / 100	3096 ms	34624 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;


const double INF = 5e18;
const int mxN = 2e5+100;
const int mxK = 32;

#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()

double dp[mxN][mxK];
set<pair<int,double>> adj[mxN];
bool on_road[mxN],vis[mxN],clean[mxN];
pair<int,double> tp;
int st=0;

bool dfs(int u){
	if(on_road[u]) return 1;
	vis[u]=1;
	for(auto it:adj[u]){
		if(!vis[it.fi]&&dfs(it.fi)){
			return on_road[u]=1;
		}
	}
}

void fnd_fz(int u=0,int par=0,double d=0){
	if(clean[u]) tp.fi=par,tp.se=d;
	for(auto it:adj[u]){
		if(it.fi^par) fnd_fz(it.fi,u,it.se);
	}
}

// dp[u][k]=minimum cost to come on node u with exactly k operation of the divide 2 type

void solve(int u,int par,int K){
	for(auto it:adj[u]){
		if(it.fi^par){
			dp[it.fi][0]=dp[u][0]+it.se;
			for(int i=1;i<=K;++i){
				dp[it.fi][i]=(dp[u][i-1]+it.se)/2;
				for(int j=1;j<i;++j){
					dp[it.fi][i]+=it.se;
					dp[it.fi][i]/=2;
				}
			}
			solve(it.fi,u,K);
		}
	}
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
	tp.fi=-1,st=0;
	for(int i=0;i<N;++i) adj[i].clear(),on_road[i]=clean[i]=vis[i]=0;
	for(int i=0;i<M;++i){
		adj[x[i]].insert({y[i],c[i]});
		adj[y[i]].insert({x[i],c[i]});
	}
	on_road[H]=1;
	dfs(0);
	vector<pair<int,double>> rem;

	// remove the extra nodes from the end
	for(auto it:adj[H]){
		if(!on_road[it.fi]) rem.pb(it);
	}
	for(auto it:rem) adj[H].erase(it);

	// remove the extra nodes from the start
	rem.clear();
	for(auto it:adj[0]){
		if(!on_road[it.fi]) rem.pb(it);
	}
	for(auto it:rem) adj[0].erase(it);

	for(int i=0;i<N;++i){
		if(arr[i]==0) clean[i]=1;
	}
	
	if(!clean[0]) fnd_fz();


	if(tp.fi!=-1){
		adj[st].erase(tp);
	}


	solve(st,-1,K);

	for(int i=0;i<N;++i){
		if(i==st) for(int j=0;j<=K;++j) dp[i][j]=0;
		else for(int j=0;j<=K;++j) dp[i][j]=INF;
	}
	
	return dp[H][K];
}

Compilation message (stderr)

cyberland.cpp: In function 'bool dfs(int)':
cyberland.cpp:28:1: warning: control reaches end of non-void function [-Wreturn-type]
   28 | }
      | ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3