제출 #1168462

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168462		rayan_bd	사이버랜드 (APIO23_cyberland)	C++20	5 / 100	1153 ms	2162688 KiB

cyberland

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

const double INF = 5e9+0.1;
const int mxN = 1e5+100;
vector<pair<int,int>> adj[mxN];

vector<int> ar;
double ans=INF;

struct DSU{
	vector<int> sz,par;
	void init(int n){
		sz.resize(n,1);
		par.resize(n);
		for(int i=1;i<n;++i) par[i]=i;
	}
	int findPar(int u){
		if(par[u]==u) return u;
		return par[u]=findPar(par[u]);
	}
	void unite(int u,int v){
		int upar=findPar(u);
		int vpar=findPar(v);
		if(upar==vpar) return;
		if(sz[upar]>sz[vpar]){
			par[vpar]=upar;
			sz[upar]+=sz[vpar];
		}else{
			par[upar]=vpar;
			sz[vpar]+=sz[upar];
		}
	}
};

double dfs(int u,int par,int h,double cost){
	if(u==h) return cost;
	if(ar[u]==2) cost/=2;
	else if(ar[u]==0) cost=0;
	double ans=INF;
	for(auto it:adj[u]){
		if(it.first^par){
			ans=min(ans,dfs(it.first,u,h,cost+it.second));
		}
	}
	return ans;
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
	ar=arr;
	DSU ds; ds.init(N+5);
	for(int i=0;i<=N;++i) adj[i].clear();
	for(int i=0;i<M;++i){
		adj[x[i]].push_back({y[i],c[i]});
		adj[y[i]].push_back({x[i],c[i]});
		ds.unite(x[i],y[i]);
	} 
	if(ds.findPar(0)!=ds.findPar(H)) return -1;
	return dfs(0,-1,H,0);
}

• Subtask 1: 5 / 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