Submission #967084

#	Time	Username	Problem	Language	Result	Execution time	Memory
967084		Batorgil952	Cyberland (APIO23_cyberland)	C++17	97 / 100	1455 ms	73732 KiB

cyberland

#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

const int N=1e5+5;
vector< pair< int, int > > v[N];
double T[N][82];
bool B[N];

int DFS(int p, int g){
	if(p==g) return 1;
	int vn=v[p].size();
	int s=0;
	for(int i=0; i<vn; i++){
		if(!B[v[p][i].ff]){
			B[v[p][i].ff]=true;
			s=max(s, DFS(v[p][i].ff, g));
		}
	}
	return s;
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
	priority_queue< pair< double, pair< ll, ll > >, vector< pair< double, pair< ll, ll > > >, greater< pair< double, pair< ll, ll > > > > q;
	
	for(int i=0; i<N; i++){
		v[i].clear();
		for(int j=0; j<=79; j++){
			T[i][j]=1000000000000000000.0;
		}
		B[i]=false;
	}
	
	for(int i=0; i<M; i++){
		v[x[i]].pb(mp(y[i], c[i]));
		v[y[i]].pb(mp(x[i], c[i]));
	}
	
	B[0]=true;
	if(DFS(0, H)==0){
		return -1;
	}
	
	if(K>=80){
		for(int i=0; i<N; i++){
			if(arr[i]==0) T[i][0]=0;
			else if(arr[i]==2) T[i][0]=0;
			else if(arr[i]==1) T[i][0]=1000000000000000000.0;
		}
		double ans=1000000000000000000.0;
		q.push(mp(0, mp(H, 0)));
		T[H][0]=0;
		T[0][0]=0;
		while(!q.empty()){
			int x=q.top().ss.ff;
			int z=q.top().ss.ss;
			double y=q.top().ff;
			q.pop();
			if(y>T[x][z]){
				continue;
			}
			int vn=v[x].size();
			double ze=0.0;
			for(int i=0; i<vn; i++){
				if(!B[v[x][i].ff]){
					continue;
				}
				if(i==0){
					ans=min(ans, T[x][0]+v[x][i].ss*1.0);
				}
				else if(arr[v[x][i].ff]==1){
					if(T[v[x][i].ff][z]>T[x][z]+v[x][i].ss*1.0){
						T[v[x][i].ff][z]=T[x][z]+v[x][i].ss*1.0;
						q.push(mp(T[v[x][i].ff][z], mp(v[x][i].ff, z)));
					}
				}
				else if(arr[v[x][i].ff]==2 || arr[v[x][i].ff]==0){
					ans=min(ans, T[x][0]+v[x][i].ss*1.0);
				}
			}
		}
		return ans;
	}
	
	q.push(mp(0, mp(0, 0)));
	for(int i=0; i<=79; i++){
		T[0][i]=0;
	}
	while(!q.empty()){
		int x=q.top().ss.ff;
		int z=q.top().ss.ss;
		double y=q.top().ff;
		q.pop();
		if(x==H){
			continue;
		}
		if(y>T[x][z] || z>K){
			continue;
		}
		int vn=v[x].size();
		double ze=0.0;
		for(int i=0; i<vn; i++){
			if(arr[v[x][i].ff]==1){
				if(T[v[x][i].ff][z]>T[x][z]+v[x][i].ss*1.0){
					T[v[x][i].ff][z]=T[x][z]+v[x][i].ss*1.0;
					q.push(mp(T[v[x][i].ff][z], mp(v[x][i].ff, z)));
				}
			}
			if(arr[v[x][i].ff]==2){
				if(T[v[x][i].ff][z+1]>(T[x][z]+v[x][i].ss*1.0)/2.0){
					T[v[x][i].ff][z+1]=(T[x][z]+v[x][i].ss*1.0)/2.0;
					q.push(mp(T[v[x][i].ff][z+1], mp(v[x][i].ff, z+1)));
				}
				if(T[v[x][i].ff][z]>T[x][z]+v[x][i].ss*1.0){
					T[v[x][i].ff][z]=T[x][z]+v[x][i].ss*1.0;
					q.push(mp(T[v[x][i].ff][z], mp(v[x][i].ff, z)));
				}
			}
			if(arr[v[x][i].ff]==0){
				if(T[v[x][i].ff][z]>ze){
					T[v[x][i].ff][z]=ze;
					q.push(mp(T[v[x][i].ff][z], mp(v[x][i].ff, z)));
				}
			}
		}
	}
	
	double ans=T[H][0];
	for(int i=1; i<=K; i++){
		ans=min(ans, T[H][i]);
	}
	return ans;
}

Compilation message (stderr)

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:69:11: warning: unused variable 'ze' [-Wunused-variable]
   69 |    double ze=0.0;
      |           ^~

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