oj.uz

Submission #968413

# Submission time Handle Problem Language Result Execution time Memory
968413 2024-04-23T11:54:03 Z Batorgil952 Cyberland (APIO23_cyberland) C++17
100 / 100
 2942 ms 71780 KB 
#include<bits/stdc++.h>

#pragma GCC optimize("O3")
 
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
 
using namespace std;
 
const int N=1e5+5;
vector< pair< int, int > > v[N];
double T[N][72];
bool B[N];
priority_queue< pair< double, pair< int, int > >, vector< pair< double, pair< int, int > > >, greater< pair< double, pair< int, int > > > > q;
 
int DFS(int p, int g){
	if(p==g) return 1;
	int vn=v[p].size();
	int s=0;
	for(int i=0; i<vn; i++){
		if(!B[v[p][i].ff]){
			B[v[p][i].ff]=true;
			s=max(s, DFS(v[p][i].ff, g));
		}
	}
	return s;
}
 
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) {
	K=min(K, 70);
	
	for(int i=0; i<N; i++){
		v[i].clear();
		for(int j=0; j<=K; j++){
			T[i][j]=1000000000000000000.0;
		}
		B[i]=false;
	}
	
	for(int i=0; i<M; i++){
		v[x[i]].pb(mp(y[i], c[i]));
		v[y[i]].pb(mp(x[i], c[i]));
	}
	
	B[0]=true;
	if(DFS(0, H)==0){
		return -1;
	}
	
	q.push(mp(0, mp(0, 0)));
	for(int i=1; i<N; i++){
		if(B[i] && arr[i]==0){
			q.push(mp(0, mp(i, 0)));
			for(int j=0; j<=K; j++){
				T[i][j]=0;
			}
		}
	}
	for(int i=0; i<=K; i++){
		T[0][i]=0;
	}
	while(!q.empty()){
		int x=q.top().ss.ff;
		int z=q.top().ss.ss;
		double y=q.top().ff;
		q.pop();
		if(x==H){
			continue;
		}
		if(y>T[x][z]){
			continue;
		}
		int vn=v[x].size();
		double ze=0.0;
		for(int i=0; i<vn; i++){
			if(arr[v[x][i].ff]==1){
				if(T[v[x][i].ff][z]>T[x][z]+v[x][i].ss*1.0){
					T[v[x][i].ff][z]=T[x][z]+v[x][i].ss*1.0;
					for(int j=z+1; j<=K; j++){
						T[v[x][i].ff][j]=min(T[v[x][i].ff][j], T[v[x][i].ff][z]);
					}
					q.push(mp(T[v[x][i].ff][z], mp(v[x][i].ff, z)));
				}
			}
			if(arr[v[x][i].ff]==2){
				if(T[v[x][i].ff][z+1]>(T[x][z]+v[x][i].ss*1.0)/2.0 && z+1<=K){
					T[v[x][i].ff][z+1]=(T[x][z]+v[x][i].ss*1.0)/2.0;
					for(int j=z+2; j<=K; j++){
						T[v[x][i].ff][j]=min(T[v[x][i].ff][j], T[v[x][i].ff][z+1]);
					}
					q.push(mp(T[v[x][i].ff][z+1], mp(v[x][i].ff, z+1)));
				}
				if(T[v[x][i].ff][z]>T[x][z]+v[x][i].ss*1.0){
					T[v[x][i].ff][z]=T[x][z]+v[x][i].ss*1.0;
					for(int j=z+1; j<=K; j++){
						T[v[x][i].ff][j]=min(T[v[x][i].ff][j], T[v[x][i].ff][z]);
					}
					q.push(mp(T[v[x][i].ff][z], mp(v[x][i].ff, z)));
				}
			}
		}
	}
	
	double ans=T[H][0];
	for(int i=1; i<=K; i++){
		ans=min(ans, T[H][i]);
	}
	return ans;
}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:77:10: warning: unused variable 'ze' [-Wunused-variable]
   77 |   double ze=0.0;
      |          ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3676 KB Correct.
2 Correct 14 ms 3676 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5964 KB Correct.
2 Correct 22 ms 5720 KB Correct.
3 Correct 28 ms 5724 KB Correct.
4 Correct 22 ms 5724 KB Correct.
5 Correct 22 ms 5720 KB Correct.
6 Correct 22 ms 10588 KB Correct.
7 Correct 27 ms 10588 KB Correct.
8 Correct 15 ms 17496 KB Correct.
9 Correct 21 ms 3928 KB Correct.
10 Correct 20 ms 3672 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5724 KB Correct.
2 Correct 23 ms 5724 KB Correct.
3 Correct 21 ms 5964 KB Correct.
4 Correct 22 ms 3800 KB Correct.
5 Correct 28 ms 3676 KB Correct.
6 Correct 7 ms 10588 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 41752 KB Correct.
2 Correct 99 ms 6240 KB Correct.
3 Correct 84 ms 6008 KB Correct.
4 Correct 85 ms 5936 KB Correct.
5 Correct 85 ms 3796 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5980 KB Correct.
2 Correct 26 ms 5976 KB Correct.
3 Correct 20 ms 5976 KB Correct.
4 Correct 21 ms 10844 KB Correct.
5 Correct 17 ms 3676 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5980 KB Correct.
2 Correct 18 ms 6004 KB Correct.
3 Correct 39 ms 52052 KB Correct.
4 Correct 14 ms 8796 KB Correct.
5 Correct 19 ms 3800 KB Correct.
6 Correct 19 ms 5976 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6036 KB Correct.
2 Correct 10 ms 6232 KB Correct.
3 Correct 325 ms 67016 KB Correct.
4 Correct 342 ms 17908 KB Correct.
5 Correct 182 ms 36288 KB Correct.
6 Correct 69 ms 15560 KB Correct.
7 Correct 307 ms 19972 KB Correct.
8 Correct 362 ms 6484 KB Correct.
9 Correct 54 ms 5980 KB Correct.
10 Correct 53 ms 6024 KB Correct.
11 Correct 364 ms 5972 KB Correct.
12 Correct 60 ms 6008 KB Correct.
13 Correct 66 ms 6196 KB Correct.
14 Correct 251 ms 34608 KB Correct.
15 Correct 325 ms 13140 KB Correct.
16 Correct 49 ms 5980 KB Correct.
17 Correct 71 ms 5976 KB Correct.
18 Correct 60 ms 5976 KB Correct.
19 Correct 161 ms 6228 KB Correct.
20 Correct 6 ms 3676 KB Correct.
21 Correct 5 ms 5720 KB Correct.
22 Correct 8 ms 6492 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 6428 KB Correct.
2 Correct 18 ms 6232 KB Correct.
3 Correct 412 ms 71780 KB Correct.
4 Correct 869 ms 9488 KB Correct.
5 Correct 482 ms 38592 KB Correct.
6 Correct 161 ms 19576 KB Correct.
7 Correct 684 ms 32748 KB Correct.
8 Correct 1135 ms 6596 KB Correct.
9 Correct 143 ms 6556 KB Correct.
10 Correct 145 ms 6352 KB Correct.
11 Correct 2137 ms 4204 KB Correct.
12 Correct 149 ms 6236 KB Correct.
13 Correct 199 ms 6860 KB Correct.
14 Correct 2320 ms 64500 KB Correct.
15 Correct 2942 ms 43920 KB Correct.
16 Correct 1635 ms 19524 KB Correct.
17 Correct 1429 ms 8528 KB Correct.
18 Correct 116 ms 7188 KB Correct.
19 Correct 213 ms 7072 KB Correct.
20 Correct 176 ms 7260 KB Correct.
21 Correct 463 ms 8604 KB Correct.
22 Correct 15 ms 3968 KB Correct.
23 Correct 10 ms 5924 KB Correct.
24 Correct 19 ms 7128 KB Correct.