oj.uz

Submission #760040

# Submission time Handle Problem Language Result Execution time Memory
760040 2023-06-17T06:58:46 Z 8e7 Cyberland (APIO23_cyberland) C++17
100 / 100
 1636 ms 16084 KB 
#include "cyberland.h"
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define ld double
#define maxn 100005
#define ff first
#define ss second
#define pii pair<ll, ll>
const ld inf = 1e15;
const ld eps = 1e-10;
vector<pii> adj[maxn];
int type[maxn];
ld d[maxn], d2[maxn];
void dijkstra(int n) {
	priority_queue<pair<ld, int> , vector<pair<ld, int> >, greater<pair<ld, int> > > pq;
	for (int i = 0;i < n;i++) {
		d2[i] = d[i];
		if (d[i] != inf) {
			pq.push(make_pair(d[i], i));
		}
	}
	while (pq.size()) {
		auto [dis, cur] = pq.top();pq.pop();
		if (abs(dis - d[cur]) > eps) continue;
		for (auto [v, w]:adj[cur]) {
			if (type[v] == 0 && d[v] > 0) {
				d[v] = 0;
				pq.push(make_pair(0, v));
			}
			if (d[cur] + w < d[v]) {
				d[v] = d[cur]+w;
				pq.push(make_pair(d[v], v));
			}
			if (type[v] == 2 && (d[cur] + w) / 2 < d2[v]) {
				d2[v] = (d[cur] + w) / 2;
			}
		}
	}
	pary(d, d + n);
	pary(d2, d2+n);
}
double solve(int N, int M, int K, int H, vector<int> U, vector<int> V, vector<int> W, vector<int> arr) {
	for (int i = 0;i < N;i++) {
		adj[i].clear();
		d[i] = d2[i] = inf;
		type[i] = arr[i];
	}
	for (int i = 0;i < M;i++) {
		if (U[i] == H) swap(U[i], V[i]);	
		adj[U[i]].push_back({V[i], W[i]});
		if (V[i] != H) adj[V[i]].push_back({U[i], W[i]});
	}
	d[0] = d2[0] = 0;
	for (int i = 0;i <= min(K, 100);i++) {
		dijkstra(N);
		if (i < K) {
			for (int j = 0;j < N;j++) {
				d[j] = min(d[j], d2[j]);
			}
		}
	}	
	if (d[H] == inf) {
		return -1;
	}
	return d[H];
}

Compilation message

cyberland.cpp: In function 'void dijkstra(int)':
cyberland.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
cyberland.cpp:52:2: note: in expansion of macro 'pary'
   52 |  pary(d, d + n);
      |  ^~~~
cyberland.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
cyberland.cpp:53:2: note: in expansion of macro 'pary'
   53 |  pary(d2, d2+n);
      |  ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2764 KB Correct.
2 Correct 35 ms 2756 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 2828 KB Correct.
2 Correct 138 ms 2984 KB Correct.
3 Correct 134 ms 2884 KB Correct.
4 Correct 143 ms 2808 KB Correct.
5 Correct 138 ms 2836 KB Correct.
6 Correct 186 ms 4220 KB Correct.
7 Correct 243 ms 4128 KB Correct.
8 Correct 107 ms 5496 KB Correct.
9 Correct 67 ms 2720 KB Correct.
10 Correct 66 ms 2716 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 2816 KB Correct.
2 Correct 143 ms 2820 KB Correct.
3 Correct 138 ms 2868 KB Correct.
4 Correct 78 ms 2644 KB Correct.
5 Correct 74 ms 2712 KB Correct.
6 Correct 40 ms 3760 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 8840 KB Correct.
2 Correct 89 ms 2808 KB Correct.
3 Correct 76 ms 2816 KB Correct.
4 Correct 82 ms 2792 KB Correct.
5 Correct 53 ms 2724 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2988 KB Correct.
2 Correct 57 ms 2904 KB Correct.
3 Correct 68 ms 2932 KB Correct.
4 Correct 97 ms 4172 KB Correct.
5 Correct 39 ms 2720 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 2988 KB Correct.
2 Correct 49 ms 2900 KB Correct.
3 Correct 38 ms 10556 KB Correct.
4 Correct 62 ms 3960 KB Correct.
5 Correct 45 ms 2728 KB Correct.
6 Correct 58 ms 3000 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 2944 KB Correct.
2 Correct 16 ms 3028 KB Correct.
3 Correct 561 ms 16004 KB Correct.
4 Correct 418 ms 6128 KB Correct.
5 Correct 306 ms 11220 KB Correct.
6 Correct 124 ms 9072 KB Correct.
7 Correct 370 ms 6116 KB Correct.
8 Correct 286 ms 3280 KB Correct.
9 Correct 75 ms 2996 KB Correct.
10 Correct 69 ms 2916 KB Correct.
11 Correct 233 ms 3016 KB Correct.
12 Correct 76 ms 2872 KB Correct.
13 Correct 72 ms 2992 KB Correct.
14 Correct 317 ms 9424 KB Correct.
15 Correct 310 ms 4588 KB Correct.
16 Correct 71 ms 2964 KB Correct.
17 Correct 87 ms 2988 KB Correct.
18 Correct 83 ms 2896 KB Correct.
19 Correct 279 ms 2840 KB Correct.
20 Correct 6 ms 2644 KB Correct.
21 Correct 7 ms 2772 KB Correct.
22 Correct 11 ms 3412 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 3012 KB Correct.
2 Correct 30 ms 2924 KB Correct.
3 Correct 1519 ms 16084 KB Correct.
4 Correct 439 ms 3844 KB Correct.
5 Correct 891 ms 11232 KB Correct.
6 Correct 325 ms 9016 KB Correct.
7 Correct 647 ms 8616 KB Correct.
8 Correct 361 ms 3208 KB Correct.
9 Correct 149 ms 2960 KB Correct.
10 Correct 150 ms 2944 KB Correct.
11 Correct 227 ms 2992 KB Correct.
12 Correct 166 ms 2960 KB Correct.
13 Correct 157 ms 2888 KB Correct.
14 Correct 1229 ms 10072 KB Correct.
15 Correct 1636 ms 9960 KB Correct.
16 Correct 663 ms 5612 KB Correct.
17 Correct 436 ms 3340 KB Correct.
18 Correct 151 ms 2984 KB Correct.
19 Correct 195 ms 2916 KB Correct.
20 Correct 179 ms 2976 KB Correct.
21 Correct 738 ms 3088 KB Correct.
22 Correct 11 ms 2644 KB Correct.
23 Correct 12 ms 2780 KB Correct.
24 Correct 25 ms 3284 KB Correct.