oj.uz

Submission #748998

# Submission time Handle Problem Language Result Execution time Memory
748998 2023-05-27T08:54:29 Z emptypringlescan Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 449536 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=100;
	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 58 ms 460 KB Correct.
2 Correct 54 ms 384 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 2032 KB Correct.
2 Correct 299 ms 2032 KB Correct.
3 Correct 280 ms 2092 KB Correct.
4 Correct 295 ms 2012 KB Correct.
5 Correct 298 ms 1984 KB Correct.
6 Correct 351 ms 16860 KB Correct.
7 Correct 455 ms 16456 KB Correct.
8 Correct 198 ms 33200 KB Correct.
9 Correct 185 ms 640 KB Correct.
10 Correct 176 ms 532 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 2128 KB Correct.
2 Correct 271 ms 2044 KB Correct.
3 Correct 277 ms 2092 KB Correct.
4 Correct 187 ms 564 KB Correct.
5 Correct 183 ms 560 KB Correct.
6 Correct 69 ms 13740 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 54024 KB Correct.
2 Correct 179 ms 1992 KB Correct.
3 Correct 157 ms 1984 KB Correct.
4 Correct 170 ms 1996 KB Correct.
5 Correct 134 ms 564 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 1892 KB Correct.
2 Correct 132 ms 1764 KB Correct.
3 Correct 163 ms 1816 KB Correct.
4 Correct 193 ms 12040 KB Correct.
5 Correct 82 ms 588 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 1888 KB Correct.
2 Correct 104 ms 1852 KB Correct.
3 Correct 67 ms 11724 KB Correct.
4 Correct 131 ms 9708 KB Correct.
5 Correct 134 ms 536 KB Correct.
6 Correct 115 ms 1884 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 1872 KB Correct.
2 Correct 23 ms 2004 KB Correct.
3 Correct 1210 ms 100856 KB Correct.
4 Correct 712 ms 27204 KB Correct.
5 Correct 639 ms 67212 KB Correct.
6 Correct 246 ms 27832 KB Correct.
7 Correct 743 ms 26552 KB Correct.
8 Correct 530 ms 5004 KB Correct.
9 Correct 158 ms 1864 KB Correct.
10 Correct 129 ms 1840 KB Correct.
11 Correct 494 ms 2152 KB Correct.
12 Correct 164 ms 2052 KB Correct.
13 Correct 137 ms 1952 KB Correct.
14 Correct 572 ms 25924 KB Correct.
15 Correct 541 ms 10180 KB Correct.
16 Correct 120 ms 1712 KB Correct.
17 Correct 155 ms 1960 KB Correct.
18 Correct 136 ms 1928 KB Correct.
19 Correct 394 ms 2036 KB Correct.
20 Correct 9 ms 468 KB Correct.
21 Correct 11 ms 1088 KB Correct.
22 Correct 17 ms 3080 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 4624 KB Correct.
2 Correct 70 ms 5180 KB Correct.
3 Execution timed out 3116 ms 449536 KB Time limit exceeded
4 Halted 0 ms 0 KB -