oj.uz

Submission #749409

# Submission time Handle Problem Language Result Execution time Memory
749409 2023-05-28T02:40:40 Z Batorgil952 Cyberland (APIO23_cyberland) C++17
49 / 100
 136 ms 24544 KB 
#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 ll N=100005;
vector< pair< ll, ll > > v[N];
double T[N][32];
bool B[N];
ll Ra[N];

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

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){
	for(ll i=0; i<N; i++){
		Ra[i]=0;
		B[i]=false;
		v[i].clear();
	}
	for(ll i=0; i<M; i++){
		ll X=x[i], Y=y[i], Z=c[i];
		v[X].pb(mp(Y, Z));
		v[Y].pb(mp(X, Z));
	}
	
	Ra[0]=1;
	B[0]=true;
	DFS(0, H);
	if(!Ra[H]) return -1;
	priority_queue< pair< double, pair< ll, ll > >, vector< pair< double, pair< ll, ll > > >, greater< pair< double, pair< ll, ll > > > > q;
	
	for(ll i=0; i<N; i++){
		if(Ra[i] && !arr[i]){
			q.push(mp(0.0, mp(0, i)));
			for(ll j=0; j<=30; j++){
				T[i][j]=0.0;
			}
		}
		else if(i==0){
			q.push(mp(0.0, mp(0, i)));
			for(ll j=0; j<=30; j++){
				T[i][j]=0.0;
			}
		}
		else{
			for(ll j=0; j<=30; j++){
				T[i][j]=1000000000000000000.0;
			}
		}
	}
	
	while(!q.empty()){
		double fx=q.top().ff;
		ll fy=q.top().ss.ff;
		ll fz=q.top().ss.ss;
		q.pop();
		if(T[fz][fy]<fx){
			continue;
		}
		if(fz==H){
			continue;
		}
		ll vn=v[fz].size();
		for(ll i=0; i<vn; i++){
			double dd=v[fz][i].ss*1.0;
			double fare=fx+dd;
			if(fare<T[v[fz][i].ff][fy]){
				if(arr[v[fz][i].ff]==0){
					continue;
				}
				if(arr[v[fz][i].ff]==1){
					q.push(mp(fare, mp(fy, v[fz][i].ff)));
					T[v[fz][i].ff][fy]=fare;
				}
				else{
					q.push(mp(fare, mp(fy, v[fz][i].ff)));
					T[v[fz][i].ff][fy]=fare;
					if(fy+1<=K && fare/2.0<T[v[fz][i].ff][fy+1]){
						fare/=2.0;
						q.push(mp(fare, mp(fy+1, v[fz][i].ff)));
						T[v[fz][i].ff][fy+1]=fare;
					}
				}
			}
		}
	}
	
	double ans=1000000000000000000.0;
	for(ll i=0; i<=K; i++){
		ans=min(ans, T[H][i]);
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2772 KB Correct.
2 Correct 19 ms 2740 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3028 KB Correct.
2 Correct 29 ms 3108 KB Correct.
3 Correct 26 ms 3028 KB Correct.
4 Correct 27 ms 3048 KB Correct.
5 Correct 28 ms 3084 KB Correct.
6 Correct 27 ms 6160 KB Correct.
7 Correct 34 ms 6040 KB Correct.
8 Correct 19 ms 9428 KB Correct.
9 Correct 24 ms 2772 KB Correct.
10 Correct 23 ms 2752 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3028 KB Correct.
2 Correct 27 ms 3096 KB Correct.
3 Correct 26 ms 3156 KB Correct.
4 Correct 27 ms 2772 KB Correct.
5 Correct 28 ms 2760 KB Correct.
6 Correct 8 ms 5716 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 24544 KB Correct.
2 Incorrect 77 ms 3248 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3156 KB Correct.
2 Correct 24 ms 3092 KB Correct.
3 Correct 25 ms 3192 KB Correct.
4 Correct 29 ms 6552 KB Correct.
5 Correct 20 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3156 KB Correct.
2 Correct 21 ms 3156 KB Correct.
3 Correct 43 ms 9760 KB Correct.
4 Correct 18 ms 5376 KB Correct.
5 Correct 24 ms 2756 KB Correct.
6 Correct 22 ms 3168 KB Correct.

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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