oj.uz

답안 #749406

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
749406 2023-05-28T02:32:38 Z Batorgil952 사이버랜드 (APIO23_cyberland) C++17
49 / 100
 132 ms 24644 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]=1000000000000000.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=1000000000000000.0;
	for(ll i=0; i<=K; i++){
		ans=min(ans, T[H][i]);
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 2772 KB Correct.
2 Correct 20 ms 2788 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 3028 KB Correct.
2 Correct 26 ms 3108 KB Correct.
3 Correct 26 ms 3108 KB Correct.
4 Correct 27 ms 3108 KB Correct.
5 Correct 28 ms 3164 KB Correct.
6 Correct 25 ms 6084 KB Correct.
7 Correct 31 ms 6048 KB Correct.
8 Correct 18 ms 9480 KB Correct.
9 Correct 24 ms 2772 KB Correct.
10 Correct 24 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 3088 KB Correct.
2 Correct 27 ms 3068 KB Correct.
3 Correct 25 ms 3164 KB Correct.
4 Correct 30 ms 2764 KB Correct.
5 Correct 28 ms 2756 KB Correct.
6 Correct 9 ms 5704 KB Correct.

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 24644 KB Correct.
2 Incorrect 78 ms 3204 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 3200 KB Correct.
2 Correct 25 ms 3156 KB Correct.
3 Correct 26 ms 3212 KB Correct.
4 Correct 27 ms 6572 KB Correct.
5 Correct 21 ms 2644 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 3212 KB Correct.
2 Correct 21 ms 3156 KB Correct.
3 Correct 43 ms 9848 KB Correct.
4 Correct 18 ms 5396 KB Correct.
5 Correct 25 ms 2644 KB Correct.
6 Correct 25 ms 3196 KB Correct.

Subtask #7
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 118 ms 3456 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 132 ms 3548 KB Wrong Answer.
2 Halted 0 ms 0 KB -