oj.uz

Submission #769916

# Submission time Handle Problem Language Result Execution time Memory
769916 2023-06-30T13:20:56 Z Dan4Life Cyberland (APIO23_cyberland) C++17
100 / 100
 810 ms 10920 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ar = pair<double,int>;
const int mxN = (int)1e5+10;
const double LINF = 1e105;
double ans;
int n, m, h;
bool vis[mxN];
double dis[mxN], dis2[mxN];
vector<pair<int,int>> adj[mxN];
priority_queue<ar,vector<ar>,greater<ar>> pq;

void dijkstra(){
	fill(vis,vis+n+1,0);
	for(int i = 0; i < n; i++) 
		if(dis[i]<LINF) pq.push({dis[i],i});
	while(!pq.empty()){
		auto [D,a] = pq.top(); pq.pop(); 
		if(vis[a] or a==h) continue; vis[a]=1;
		for(auto [b,w] : adj[a]) if(dis[b]>dis[a]+w) 
			dis[b]=dis[a]+w, pq.push({dis[b],b});
	}
	ans = min(ans, dis[h]);
}

double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi A) {
	n = N, m = M, h = H, K = min(K, 67);
	fill(dis,dis+n,LINF); ans = LINF;
	for(int i = 0; i < n; i++) adj[i].clear();
	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]});
	dis[0]=0; dijkstra(); if(dis[h]>=LINF) return -1;
	for(int i = 0; i < n; i++)
		if(dis[i]!=LINF) dis[i]=A[i]&&i?LINF:0;
	for(int i = 0; i <= K; i++){
		dijkstra(); fill(dis2,dis2+n,LINF);
		for(int j = 0; j < n; j++)
			if(A[j]>1) for(auto [u,w] : adj[j])
				dis2[u]=min(dis2[u],dis[j]/2+w);
		for(int j = 0; j < n; j++) dis[j]=dis2[j];
	}
	return ans;
}

Compilation message

cyberland.cpp: In function 'void dijkstra()':
cyberland.cpp:21:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   21 |   if(vis[a] or a==h) continue; vis[a]=1;
      |   ^~
cyberland.cpp:21:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   21 |   if(vis[a] or a==h) continue; vis[a]=1;
      |                                ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2780 KB Correct.
2 Correct 18 ms 2744 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2848 KB Correct.
2 Correct 30 ms 2840 KB Correct.
3 Correct 25 ms 2772 KB Correct.
4 Correct 31 ms 2792 KB Correct.
5 Correct 27 ms 2772 KB Correct.
6 Correct 29 ms 3468 KB Correct.
7 Correct 31 ms 3504 KB Correct.
8 Correct 15 ms 4408 KB Correct.
9 Correct 23 ms 2644 KB Correct.
10 Correct 22 ms 2720 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2788 KB Correct.
2 Correct 27 ms 2804 KB Correct.
3 Correct 33 ms 2832 KB Correct.
4 Correct 26 ms 2644 KB Correct.
5 Correct 26 ms 2720 KB Correct.
6 Correct 6 ms 3540 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 7932 KB Correct.
2 Correct 139 ms 2796 KB Correct.
3 Correct 127 ms 2828 KB Correct.
4 Correct 128 ms 2800 KB Correct.
5 Correct 73 ms 2712 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2852 KB Correct.
2 Correct 22 ms 2868 KB Correct.
3 Correct 21 ms 2864 KB Correct.
4 Correct 23 ms 3588 KB Correct.
5 Correct 19 ms 2644 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2868 KB Correct.
2 Correct 19 ms 2900 KB Correct.
3 Correct 32 ms 8364 KB Correct.
4 Correct 15 ms 3476 KB Correct.
5 Correct 21 ms 2716 KB Correct.
6 Correct 21 ms 2900 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 3040 KB Correct.
2 Correct 15 ms 2772 KB Correct.
3 Correct 291 ms 10920 KB Correct.
4 Correct 215 ms 4544 KB Correct.
5 Correct 337 ms 8428 KB Correct.
6 Correct 127 ms 7112 KB Correct.
7 Correct 219 ms 4672 KB Correct.
8 Correct 167 ms 3100 KB Correct.
9 Correct 73 ms 2924 KB Correct.
10 Correct 69 ms 2840 KB Correct.
11 Correct 145 ms 2900 KB Correct.
12 Correct 83 ms 2788 KB Correct.
13 Correct 77 ms 2832 KB Correct.
14 Correct 228 ms 6824 KB Correct.
15 Correct 194 ms 3816 KB Correct.
16 Correct 71 ms 2804 KB Correct.
17 Correct 93 ms 2844 KB Correct.
18 Correct 80 ms 2784 KB Correct.
19 Correct 247 ms 2800 KB Correct.
20 Correct 5 ms 2652 KB Correct.
21 Correct 7 ms 2644 KB Correct.
22 Correct 10 ms 3112 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 2772 KB Correct.
2 Correct 27 ms 2772 KB Correct.
3 Correct 175 ms 10504 KB Correct.
4 Correct 238 ms 3332 KB Correct.
5 Correct 676 ms 8424 KB Correct.
6 Correct 223 ms 7144 KB Correct.
7 Correct 398 ms 6176 KB Correct.
8 Correct 187 ms 2976 KB Correct.
9 Correct 116 ms 2884 KB Correct.
10 Correct 105 ms 2820 KB Correct.
11 Correct 125 ms 2904 KB Correct.
12 Correct 143 ms 2800 KB Correct.
13 Correct 148 ms 2892 KB Correct.
14 Correct 810 ms 7372 KB Correct.
15 Correct 643 ms 7040 KB Correct.
16 Correct 350 ms 4360 KB Correct.
17 Correct 217 ms 3140 KB Correct.
18 Correct 117 ms 2808 KB Correct.
19 Correct 168 ms 2820 KB Correct.
20 Correct 145 ms 2816 KB Correct.
21 Correct 471 ms 2800 KB Correct.
22 Correct 7 ms 2644 KB Correct.
23 Correct 10 ms 2644 KB Correct.
24 Correct 17 ms 3156 KB Correct.