제출 #1171867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171867		rayan_bd	Cyberland (APIO23_cyberland)	C++20	0 / 100	3096 ms	34372 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;
vector<int> ar;
int st=0,last;

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=-1,double d=0){
	if(clean[u]) st=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){
			for(int i=0;i<=K;++i) dp[it.fi][i]=dp[u][i]+it.se;
			if(ar[it.fi]==2&&it.fi!=last){
				for(int k=1;k<=K;++k){
					for(int prev=0;prev<k;++prev){
						double curr=dp[u][prev];
						if(k==1) dp[it.fi][k]=min(dp[it.fi][k],curr+it.se);
						for(int i=0;i<k-prev-1;++i){
							curr+=it.se*(i==0?1:2);
							curr/=2;
							dp[it.fi][k]=min(dp[it.fi][k],curr);
						}
					}
				}
			}
			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){
	ar=arr,tp.fi=-1,st=0,last=H;
	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]});
		//cout<<x[i]<<" "<<y[i]<<" "<<c[i]<<endl;
	}
	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);
	//	cout<<it.fi<<endl;
	}
	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);
		// cout<<it.fi<<endl;
	}

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


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

	//for(auto it:adj[st]) cout<<it.fi<<endl;

	//cout<<st<<endl;

	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;
	}

	solve(st,-1,K);


	double ans=INF;
	for(int i=0;i<=K;++i) ans=min(ans,dp[H][i]);
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• 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