Submission #749415

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
749415	2023-05-28T02:47:24 Z	Batorgil952	Cyberland (APIO23_cyberland)	C++17	97 / 100	858 ms	68556 KB

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 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(arr[v[fz][i].ff]==1){
				if(fare<T[v[fz][i].ff][fy]){
					q.push(mp(fare, mp(fy, v[fz][i].ff)));
					T[v[fz][i].ff][fy]=fare;
				}
			}
			if(arr[v[fz][i].ff]==2){
				if(fare<T[v[fz][i].ff][fy]){
					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	2752 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	3100 KB	Correct.
2	Correct	28 ms	3112 KB	Correct.
3	Correct	27 ms	3116 KB	Correct.
4	Correct	27 ms	3156 KB	Correct.
5	Correct	26 ms	3028 KB	Correct.
6	Correct	25 ms	6104 KB	Correct.
7	Correct	33 ms	6056 KB	Correct.
8	Correct	17 ms	9492 KB	Correct.
9	Correct	25 ms	2752 KB	Correct.
10	Correct	24 ms	2644 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	3120 KB	Correct.
2	Correct	27 ms	3096 KB	Correct.
3	Correct	26 ms	3128 KB	Correct.
4	Correct	26 ms	2768 KB	Correct.
5	Correct	26 ms	2760 KB	Correct.
6	Correct	8 ms	5716 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	179 ms	26196 KB	Correct.
2	Correct	229 ms	3388 KB	Correct.
3	Correct	192 ms	3496 KB	Correct.
4	Correct	201 ms	3384 KB	Correct.
5	Correct	185 ms	2812 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	3216 KB	Correct.
2	Correct	24 ms	3216 KB	Correct.
3	Correct	22 ms	3148 KB	Correct.
4	Correct	27 ms	6580 KB	Correct.
5	Correct	20 ms	2764 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	3240 KB	Correct.
2	Correct	21 ms	3180 KB	Correct.
3	Correct	42 ms	9752 KB	Correct.
4	Correct	17 ms	5396 KB	Correct.
5	Correct	23 ms	2760 KB	Correct.
6	Correct	22 ms	3228 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	198 ms	3828 KB	Correct.
2	Correct	33 ms	4524 KB	Correct.
3	Correct	720 ms	38768 KB	Correct.
4	Correct	541 ms	11656 KB	Correct.
5	Correct	858 ms	68556 KB	Correct.
6	Correct	436 ms	36188 KB	Correct.
7	Correct	533 ms	12092 KB	Correct.
8	Correct	515 ms	4300 KB	Correct.
9	Correct	184 ms	4328 KB	Correct.
10	Correct	171 ms	4404 KB	Correct.
11	Correct	497 ms	3636 KB	Correct.
12	Correct	193 ms	4396 KB	Correct.
13	Correct	207 ms	4356 KB	Correct.
14	Correct	464 ms	21616 KB	Correct.
15	Correct	519 ms	8168 KB	Correct.
16	Correct	177 ms	4288 KB	Correct.
17	Correct	221 ms	4144 KB	Correct.
18	Correct	202 ms	4016 KB	Correct.
19	Correct	449 ms	3772 KB	Correct.
20	Correct	15 ms	2980 KB	Correct.
21	Correct	15 ms	3444 KB	Correct.
22	Correct	35 ms	6824 KB	Correct.

Subtask #8
0.0 / 3.0

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

Submission #749415

Compilation message