oj.uz

Submission #749407

# Submission time Handle Problem Language Result Execution time Memory
749407 2023-05-28T02:36:03 Z Batorgil952 Cyberland (APIO23_cyberland) C++17
49 / 100
 139 ms 24628 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]==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] && arr[v[fz][i].ff]==2){
						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 2744 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3032 KB Correct.
2 Correct 27 ms 3112 KB Correct.
3 Correct 35 ms 3108 KB Correct.
4 Correct 32 ms 3028 KB Correct.
5 Correct 31 ms 3104 KB Correct.
6 Correct 28 ms 6092 KB Correct.
7 Correct 33 ms 6100 KB Correct.
8 Correct 20 ms 9408 KB Correct.
9 Correct 27 ms 2748 KB Correct.
10 Correct 28 ms 2760 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3088 KB Correct.
2 Correct 35 ms 3148 KB Correct.
3 Correct 27 ms 3128 KB Correct.
4 Correct 26 ms 2748 KB Correct.
5 Correct 30 ms 2752 KB Correct.
6 Correct 9 ms 5716 KB Correct.

Subtask #4
0.0 / 19.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3216 KB Correct.
2 Correct 26 ms 3196 KB Correct.
3 Correct 24 ms 3200 KB Correct.
4 Correct 27 ms 6640 KB Correct.
5 Correct 24 ms 2760 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3208 KB Correct.
2 Correct 24 ms 3236 KB Correct.
3 Correct 43 ms 9784 KB Correct.
4 Correct 18 ms 5396 KB Correct.
5 Correct 23 ms 2744 KB Correct.
6 Correct 25 ms 3156 KB Correct.

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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