oj.uz

Submission #782852

# Submission time Handle Problem Language Result Execution time Memory
782852 2023-07-14T10:27:27 Z vjudge1 Cyberland (APIO23_cyberland) C++17
49 / 100
 35 ms 9816 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2772 KB Correct.
2 Correct 16 ms 3028 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2800 KB Correct.
2 Correct 25 ms 2772 KB Correct.
3 Correct 23 ms 2772 KB Correct.
4 Correct 24 ms 2824 KB Correct.
5 Correct 25 ms 2772 KB Correct.
6 Correct 23 ms 3624 KB Correct.
7 Correct 28 ms 3612 KB Correct.
8 Correct 13 ms 4692 KB Correct.
9 Correct 22 ms 2720 KB Correct.
10 Correct 22 ms 2644 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2812 KB Correct.
2 Correct 25 ms 2816 KB Correct.
3 Correct 24 ms 2836 KB Correct.
4 Correct 23 ms 2732 KB Correct.
5 Correct 26 ms 2736 KB Correct.
6 Correct 6 ms 3412 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 4436 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2944 KB Correct.
2 Correct 23 ms 2916 KB Correct.
3 Correct 23 ms 2880 KB Correct.
4 Correct 25 ms 4072 KB Correct.
5 Correct 19 ms 2644 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2864 KB Correct.
2 Correct 23 ms 2916 KB Correct.
3 Correct 35 ms 9816 KB Correct.
4 Correct 17 ms 3788 KB Correct.
5 Correct 23 ms 2728 KB Correct.
6 Correct 27 ms 2900 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 2644 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 2644 KB Wrong Answer.
2 Halted 0 ms 0 KB -