oj.uz

Submission #769897

# Submission time Handle Problem Language Result Execution time Memory
769897 2023-06-30T12:44:14 Z Dan4Life Cyberland (APIO23_cyberland) C++17
100 / 100
 805 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]==2) 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 22 ms 2840 KB Correct.
2 Correct 19 ms 2816 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2772 KB Correct.
2 Correct 26 ms 2772 KB Correct.
3 Correct 30 ms 2756 KB Correct.
4 Correct 25 ms 2788 KB Correct.
5 Correct 26 ms 2772 KB Correct.
6 Correct 23 ms 3568 KB Correct.
7 Correct 30 ms 3500 KB Correct.
8 Correct 14 ms 4404 KB Correct.
9 Correct 22 ms 2724 KB Correct.
10 Correct 22 ms 2736 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2808 KB Correct.
2 Correct 27 ms 2840 KB Correct.
3 Correct 26 ms 2860 KB Correct.
4 Correct 26 ms 2728 KB Correct.
5 Correct 26 ms 2724 KB Correct.
6 Correct 6 ms 3540 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 7928 KB Correct.
2 Correct 138 ms 2804 KB Correct.
3 Correct 126 ms 2772 KB Correct.
4 Correct 136 ms 2768 KB Correct.
5 Correct 75 ms 2780 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2900 KB Correct.
2 Correct 21 ms 2820 KB Correct.
3 Correct 22 ms 2772 KB Correct.
4 Correct 22 ms 3668 KB Correct.
5 Correct 18 ms 2716 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2808 KB Correct.
2 Correct 20 ms 2876 KB Correct.
3 Correct 32 ms 8492 KB Correct.
4 Correct 15 ms 3520 KB Correct.
5 Correct 21 ms 2644 KB Correct.
6 Correct 21 ms 2904 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 2804 KB Correct.
2 Correct 16 ms 2772 KB Correct.
3 Correct 290 ms 10920 KB Correct.
4 Correct 215 ms 4588 KB Correct.
5 Correct 310 ms 8424 KB Correct.
6 Correct 116 ms 7048 KB Correct.
7 Correct 218 ms 4736 KB Correct.
8 Correct 165 ms 3080 KB Correct.
9 Correct 69 ms 2800 KB Correct.
10 Correct 70 ms 2888 KB Correct.
11 Correct 142 ms 3008 KB Correct.
12 Correct 94 ms 2904 KB Correct.
13 Correct 78 ms 2852 KB Correct.
14 Correct 205 ms 6696 KB Correct.
15 Correct 191 ms 3772 KB Correct.
16 Correct 74 ms 2892 KB Correct.
17 Correct 107 ms 2804 KB Correct.
18 Correct 79 ms 2852 KB Correct.
19 Correct 244 ms 2780 KB Correct.
20 Correct 5 ms 2644 KB Correct.
21 Correct 7 ms 2644 KB Correct.
22 Correct 10 ms 3156 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 2776 KB Correct.
2 Correct 27 ms 2900 KB Correct.
3 Correct 176 ms 10572 KB Correct.
4 Correct 247 ms 3332 KB Correct.
5 Correct 658 ms 8464 KB Correct.
6 Correct 230 ms 7240 KB Correct.
7 Correct 376 ms 6092 KB Correct.
8 Correct 186 ms 2928 KB Correct.
9 Correct 121 ms 2808 KB Correct.
10 Correct 106 ms 2828 KB Correct.
11 Correct 111 ms 2856 KB Correct.
12 Correct 144 ms 2872 KB Correct.
13 Correct 131 ms 2896 KB Correct.
14 Correct 805 ms 7364 KB Correct.
15 Correct 688 ms 7016 KB Correct.
16 Correct 346 ms 4364 KB Correct.
17 Correct 215 ms 3124 KB Correct.
18 Correct 119 ms 2876 KB Correct.
19 Correct 167 ms 2780 KB Correct.
20 Correct 135 ms 2772 KB Correct.
21 Correct 474 ms 2776 KB Correct.
22 Correct 8 ms 2684 KB Correct.
23 Correct 10 ms 2644 KB Correct.
24 Correct 17 ms 3204 KB Correct.