Submission #782852

#	Time	Username	Problem	Language	Result	Execution time	Memory
782852		vjudge1	Cyberland (APIO23_cyberland)	C++17	49 / 100	35 ms	9816 KiB

cyberland

#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ll long long
#define pb push_back
#define uwu 100005 
vector<pair<int,int>>adj[uwu];
double noiki(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){int father[N];
	for(int i=0;i<M;i++){
		adj[x[i]].pb({y[i],c[i]});
		adj[y[i]].pb({x[i],c[i]});
	}
	ll int yol[N];
	for(int i=0;i<N;i++){
		father[i]=-1;
		yol[i]=1000000000000000000;
	}
	priority_queue<tuple<ll int,int,int>> pq;
	pq.push({(ll int)0,0,-1});
	while(pq.size()){
		ll int node,once, deg;
		tie(deg,node,once)=pq.top();deg=-deg;
		pq.pop();
		if(arr[node]==0){
			deg=0;
		}
		if(yol[node]<=deg)continue;
		yol[node]=deg;

		father[node]=once;
		if(node==H)continue;
		for(auto u:adj[node]){
			ll int kim=u.first, lira=u.second+deg;
			pq.push({-lira,kim,node});
			
		}
	}
	for(int i=0;i<N;i++)adj[i].clear();
	if(yol[H]==1000000000000000000)yol[H]=-1;
	return (1.0)*(double)yol[H];
}
double uc(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){
	int kim[3][3];
	for(int i=0;i<M;i++){
		adj[x[i]].pb({y[i],c[i]});
		adj[y[i]].pb({x[i],c[i]});
	}
	for(int i=0;i<3;i++){for(int j=0;j<3;j++)kim[i][j]=1000000007;}
	for(int i=0;i<M;i++){
		kim[x[i]][y[i]]=min(kim[x[i]][y[i]],c[i]);
		kim[y[i]][x[i]]=min(kim[y[i]][x[i]],c[i]);
	}
	double yol[N];
	for(int i=0;i<N;i++){
		yol[i]=1000000000000000000;
	}
	if(H==0)return 0;
	if(N==3){
		if(H==2&&kim[0][H]!=1000000007&&kim[0][1]==1000000007) return kim[0][H]/((arr[H]==2&&K)?2.0:1.0);
		
		if(H==1&&kim[0][H]!=1000000007&&kim[0][2]==1000000007) return kim[0][H]/((arr[H]==2&&K)?2.0:1.0);


		priority_queue<tuple<double,int,int>> pq;
		pq.push({-0.0,0,0});
		while(pq.size()){
			int node,kac;double deg;
			tie(deg,node,kac)=pq.top();deg=-deg;
			pq.pop();
			if(arr[node]==0)deg=0;
			if(arr[node]==2&&kac<K){
				deg=deg/2;
				kac++;
			}
			if(yol[node]<=deg)continue;
			yol[node]=deg;
			if(node==H)continue;
			for(auto u:adj[node]){
				int ner=u.first;double lira=u.second+deg;
				pq.push({-lira,ner,kac});
			}
		}
		if(yol[H]==1000000000000000000)yol[H]=-1;
		return yol[H];
	}
	if(N==2){
		if(kim[0][H]==1000000007)return -1;
		if(arr[H]==0)return 0;
		if(arr[H]==2&&K)return kim[0][H]/2.0;
		return kim[0][H];
	}



	
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){
	int yes=0;
	for(int i=0;i<N;i++){
		if(arr[i]==2){
			yes=1;break;
		}
	}

	double cev;
	if(yes==0)return noiki(N, M, K, H,x, y, c, arr);
	if(N<=3) cev=uc(N, M, K, H,x, y, c, arr);


	for(int i=0;i<N;i++)adj[i].clear();
	return cev;
}

Compilation message (stderr)

cyberland.cpp: In function 'double noiki(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:9:107: warning: variable 'father' set but not used [-Wunused-but-set-variable]
    9 | double noiki(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){int father[N];
      |                                                                                                           ^~~~~~
cyberland.cpp: In function 'double uc(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:97:1: warning: control reaches end of non-void function [-Wreturn-type]
   97 | }
      | ^
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:112:9: warning: 'cev' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |  return cev;
      |         ^~~

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