Submission #927929

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
927929	2024-02-15T14:09:12 Z	TAhmed33	Cyberland (APIO23_cyberland)	C++17	100 / 100	2128 ms	144396 KB

cyberland

#include <bits/stdc++.h>
using namespace std;
double pre[100];
double solve (int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    k = min(k, 70);
    pre[0] = 1;
    for(int i = 1; i <= k;i++) {
        pre[i] = pre[i-1]/2;
    }
	long double dist[n][k + 1];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= k; j++) {
			dist[i][j] = 1e18;
		}
	}
	dist[0][k] = 0;
	vector <pair <int, long double>> adj[n];
	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]});
	}
	priority_queue <pair <long double, int>, vector <pair <long double, int>>, greater <pair <long double, int>>> pq[k + 1];
	pq[k].push({0, 0});
	for (int i = k; i >= 0; i--) {
		while (!pq[i].empty()) {
			auto l = pq[i].top(); pq[i].pop();
			if (dist[l.second][i] < l.first) continue;
			if (l.second == h) continue;
			for (auto j : adj[l.second]) {
				long double sum = l.first + j.second;
				if (dist[j.first][i] > sum) {
					dist[j.first][i] = sum; pq[i].push({sum, j.first});
				}
				if (arr[j.first] == 0) {
					sum = 0;
					if (dist[j.first][i] > sum) {
						dist[j.first][i] = sum; pq[i].push({sum, j.first});
					}
				} else if (arr[j.first] == 1) {
					continue;
				} else {
					if (i == 0) continue;
					sum *= pre[1];
					if (dist[j.first][i - 1] > sum) {
						dist[j.first][i - 1] = sum;
						pq[i - 1].push({sum, j.first});
					}
				}
			}
		}
	}
	long double mn = 1e18;
	for (int i = 0; i <= k; i++) mn = min(mn, dist[h][i]);
	if (mn == 1e18) {
		return -1;
	}
	return mn;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	796 KB	Correct.
2	Correct	24 ms	820 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	1884 KB	Correct.
2	Correct	36 ms	2052 KB	Correct.
3	Correct	34 ms	2004 KB	Correct.
4	Correct	35 ms	1972 KB	Correct.
5	Correct	36 ms	1980 KB	Correct.
6	Correct	30 ms	7692 KB	Correct.
7	Correct	43 ms	7508 KB	Correct.
8	Correct	25 ms	13144 KB	Correct.
9	Correct	29 ms	1452 KB	Correct.
10	Correct	29 ms	1372 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	2076 KB	Correct.
2	Correct	41 ms	1884 KB	Correct.
3	Correct	37 ms	1872 KB	Correct.
4	Correct	39 ms	1632 KB	Correct.
5	Correct	45 ms	1440 KB	Correct.
6	Correct	10 ms	5724 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	213 ms	44752 KB	Correct.
2	Correct	218 ms	2500 KB	Correct.
3	Correct	193 ms	2496 KB	Correct.
4	Correct	207 ms	2460 KB	Correct.
5	Correct	122 ms	1360 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	1880 KB	Correct.
2	Correct	40 ms	2128 KB	Correct.
3	Correct	30 ms	2132 KB	Correct.
4	Correct	34 ms	7452 KB	Correct.
5	Correct	27 ms	1368 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	2024 KB	Correct.
2	Correct	32 ms	1884 KB	Correct.
3	Correct	67 ms	50004 KB	Correct.
4	Correct	26 ms	5848 KB	Correct.
5	Correct	32 ms	1280 KB	Correct.
6	Correct	35 ms	2128 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	239 ms	2680 KB	Correct.
2	Correct	37 ms	2756 KB	Correct.
3	Correct	900 ms	45892 KB	Correct.
4	Correct	461 ms	13684 KB	Correct.
5	Correct	897 ms	71220 KB	Correct.
6	Correct	330 ms	37452 KB	Correct.
7	Correct	441 ms	12648 KB	Correct.
8	Correct	338 ms	4240 KB	Correct.
9	Correct	191 ms	2676 KB	Correct.
10	Correct	184 ms	2524 KB	Correct.
11	Correct	304 ms	2992 KB	Correct.
12	Correct	241 ms	2724 KB	Correct.
13	Correct	238 ms	2776 KB	Correct.
14	Correct	409 ms	14984 KB	Correct.
15	Correct	389 ms	6820 KB	Correct.
16	Correct	196 ms	2732 KB	Correct.
17	Correct	268 ms	2824 KB	Correct.
18	Correct	235 ms	2800 KB	Correct.
19	Correct	680 ms	3856 KB	Correct.
20	Correct	15 ms	604 KB	Correct.
21	Correct	20 ms	1440 KB	Correct.
22	Correct	26 ms	3932 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	532 ms	4048 KB	Correct.
2	Correct	74 ms	4956 KB	Correct.
3	Correct	1307 ms	127548 KB	Correct.
4	Correct	479 ms	7996 KB	Correct.
5	Correct	2049 ms	144396 KB	Correct.
6	Correct	764 ms	70368 KB	Correct.
7	Correct	853 ms	32888 KB	Correct.
8	Correct	448 ms	4588 KB	Correct.
9	Correct	408 ms	4144 KB	Correct.
10	Correct	407 ms	3868 KB	Correct.
11	Correct	221 ms	1656 KB	Correct.
12	Correct	486 ms	4296 KB	Correct.
13	Correct	463 ms	4172 KB	Correct.
14	Correct	2128 ms	85012 KB	Correct.
15	Correct	1743 ms	68736 KB	Correct.
16	Correct	727 ms	25592 KB	Correct.
17	Correct	519 ms	7596 KB	Correct.
18	Correct	439 ms	4388 KB	Correct.
19	Correct	525 ms	4336 KB	Correct.
20	Correct	504 ms	4304 KB	Correct.
21	Correct	1470 ms	5324 KB	Correct.
22	Correct	26 ms	768 KB	Correct.
23	Correct	34 ms	2668 KB	Correct.
24	Correct	55 ms	7252 KB	Correct.

Submission #927929

Compilation message