oj.uz

Submission #748999

# Submission time Handle Problem Language Result Execution time Memory
748999 2023-05-27T08:55:52 Z emptypringlescan Cyberland (APIO23_cyberland) C++17
97 / 100
 2429 ms 321012 KB 
#include <bits/stdc++.h>
using namespace std;

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){
	vector<pair<int,long double> > adj[N];
	int n=N,m=M,k=K,h=H;
	int sz=64;
	k=min(k,sz-1);
	for(int i=0; i<m; i++){
		adj[x[i]].push_back({y[i],c[i]});
		adj[y[i]].push_back({x[i],c[i]});
	}
	int can[n];
	memset(can,0,sizeof(can));
	queue<int> q;
	q.push(0);
	while(!q.empty()){
		int a=q.front();
		q.pop();
		if(can[a]) continue;
		can[a]=1;
		for(auto i:adj[a]){
			if(!can[i.first]&&i.first!=h) q.push(i.first);
			if(i.first==h) can[h]=1;
		}
	}
	if(!can[h]) return -1;
	long double dist[k+5][n];
	for(int j=0; j<k+5; j++) for(int i=0; i<n; i++) dist[j][i]=1e16;
	priority_queue<pair<long double,int>,vector<pair<long double,int>>,greater<pair<long double,int> > > pq[k+5];
	pq[0].push({0,0});
	for(int i=1; i<n; i++){
		if(arr[i]==0&&can[i]){
			pq[0].push({0,i});
		}
	}
	for(int i=0; i<=k; i++){
		if(i){
			for(int j=0; j<n; j++) dist[i][j]=min(dist[i][j],dist[i-1][j]);
			for(int j=0; j<n; j++) if(can[j]) pq[i].push({dist[i][j],j});
		}
		while(!pq[i].empty()){
			long double a=pq[i].top().first;
			int b=pq[i].top().second;
			pq[i].pop();
			if(dist[i][b]<a) continue;
			dist[i][b]=a;
			if(b==h) continue;
			long double cc=a/(long double)2.0;
			for(auto j:adj[b]){
				if(dist[i][j.first]>a+j.second){
					pq[i].push({a+j.second,j.first});
				}
				if(i<k&&arr[b]==2){
					if(dist[i+1][j.first]>cc+j.second){
						dist[i+1][j.first]=cc+j.second;
					}
				}
			}
		}
	}
	return (double)dist[k][h];
}/*
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << solve(3,3,1,2,{0,0,1},{1,2,2},{10000,500000,1},{1,2,1});
}*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 440 KB Correct.
2 Correct 57 ms 364 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 2020 KB Correct.
2 Correct 294 ms 2172 KB Correct.
3 Correct 288 ms 2100 KB Correct.
4 Correct 316 ms 2016 KB Correct.
5 Correct 310 ms 2044 KB Correct.
6 Correct 342 ms 16760 KB Correct.
7 Correct 457 ms 16508 KB Correct.
8 Correct 236 ms 33228 KB Correct.
9 Correct 193 ms 540 KB Correct.
10 Correct 176 ms 556 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 2052 KB Correct.
2 Correct 281 ms 2092 KB Correct.
3 Correct 258 ms 2260 KB Correct.
4 Correct 189 ms 560 KB Correct.
5 Correct 188 ms 564 KB Correct.
6 Correct 72 ms 13820 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 53968 KB Correct.
2 Correct 182 ms 2016 KB Correct.
3 Correct 156 ms 2048 KB Correct.
4 Correct 179 ms 1964 KB Correct.
5 Correct 122 ms 596 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 1920 KB Correct.
2 Correct 122 ms 1788 KB Correct.
3 Correct 129 ms 1808 KB Correct.
4 Correct 185 ms 12048 KB Correct.
5 Correct 78 ms 540 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 1976 KB Correct.
2 Correct 99 ms 1840 KB Correct.
3 Correct 48 ms 11780 KB Correct.
4 Correct 103 ms 9696 KB Correct.
5 Correct 95 ms 468 KB Correct.
6 Correct 128 ms 1936 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 1884 KB Correct.
2 Correct 27 ms 2004 KB Correct.
3 Correct 1207 ms 100796 KB Correct.
4 Correct 802 ms 27128 KB Correct.
5 Correct 623 ms 67236 KB Correct.
6 Correct 222 ms 27720 KB Correct.
7 Correct 695 ms 26468 KB Correct.
8 Correct 534 ms 4992 KB Correct.
9 Correct 124 ms 1896 KB Correct.
10 Correct 125 ms 1768 KB Correct.
11 Correct 483 ms 2120 KB Correct.
12 Correct 164 ms 1972 KB Correct.
13 Correct 144 ms 1976 KB Correct.
14 Correct 617 ms 26004 KB Correct.
15 Correct 551 ms 10244 KB Correct.
16 Correct 127 ms 1668 KB Correct.
17 Correct 157 ms 1940 KB Correct.
18 Correct 133 ms 1840 KB Correct.
19 Correct 401 ms 2016 KB Correct.
20 Correct 10 ms 512 KB Correct.
21 Correct 10 ms 1128 KB Correct.
22 Correct 17 ms 3112 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 3152 KB Correct.
2 Correct 41 ms 3548 KB Correct.
3 Incorrect 2429 ms 321012 KB Wrong Answer.
4 Halted 0 ms 0 KB -