Submission #1071959

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1071959	2024-08-23T12:45:10 Z	Halym2007	Cyberland (APIO23_cyberland)	C++17	100 / 100	1581 ms	85328 KB

cyberland

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <double, int>
const int N = 2e5 + 5;
const int git = 70;
vector <pair <int, int>> v[N];
double dis[git][N];
set <pii> q[N];
int n, m, k, h;
double jogap = 1e16;
bool vis[N];
 
void dfs (ll x) {
	vis[x] = 1;
	for (auto i : v[x]) {
		if (vis[i.ff]) continue;
		dfs(i.ff);
	}
}
 
 
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
	n = N;m = M;k = K;h = H;
	for (int i = 0; i < m; ++i) {
		v[x[i]].pb ({y[i], c[i]});
		v[y[i]].pb ({x[i], c[i]});
	}
	jogap = 1e16;
	vis[h] = 1;
	if (k >= git - 1) k = git - 2;
	dfs (0);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < git; ++j) {
			dis[j][i] = 1e16;
		}
	}
	q[0].insert ({0, 0});
	dis[0][0] = 0;
	for (int i = 0; i < n; ++i) {
		if (!a[i] and vis[i]) {
			q[0].insert ({0, i});
			dis[0][i] = 0;
		}
	}
	for (int i = 0; i <= k; ++i) {
		while (!q[i].empty()) {
			int x = (*q[i].begin()).ss;
			q[i].erase(q[i].begin());
			if (x == h) continue;
			for (auto j : v[x]) {
				double val = dis[i][x] + j.ss;
				if (val < dis[i][j.ff]) {
					dis[i][j.ff] = val;
					q[i].insert ({val, j.ff});
				}
				if (a[j.ff] == 2) {
					val /= 2;
					if (dis[i + 1][j.ff] > val) {
						dis[i + 1][j.ff] =  val;
						q[i + 1].insert ({val, j.ff});
					}
				}
			} 
		}
		jogap = min (jogap, dis[i][h]);
	}
	
	if (jogap == (double)1e16) jogap = -1;
	for (int i = 0; i < n; ++i) {
		v[i].clear();
		vis[i] = 0;
	}
	for (int i = 0; i < git; ++i) {
		q[i].clear();
	}
	return jogap;
}
 
 
//int main() {
//	freopen ("input.txt", "r", stdin);
//  int T;
//  assert(1 == scanf("%d", &T));
//  while (T--){
//    int N,M,K,H;
//    assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
//    std::vector<int> x(M);
//    std::vector<int> y(M);
//    std::vector<int> c(M);
//    std::vector<int> arr(N);
//    for (int i=0;i<N;i++)
//      assert(1 == scanf("%d", &arr[i]));
//    for (int i=0;i<M;i++)
//      assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
//    printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
//  }
//}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	30300 KB	Correct.
2	Correct	19 ms	24152 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	24668 KB	Correct.
2	Correct	23 ms	24668 KB	Correct.
3	Correct	29 ms	32856 KB	Correct.
4	Correct	26 ms	32604 KB	Correct.
5	Correct	28 ms	26716 KB	Correct.
6	Correct	27 ms	37464 KB	Correct.
7	Correct	43 ms	35420 KB	Correct.
8	Correct	30 ms	40796 KB	Correct.
9	Correct	24 ms	32088 KB	Correct.
10	Correct	22 ms	24152 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	24668 KB	Correct.
2	Correct	27 ms	32600 KB	Correct.
3	Correct	25 ms	30812 KB	Correct.
4	Correct	25 ms	30296 KB	Correct.
5	Correct	32 ms	24088 KB	Correct.
6	Correct	15 ms	28764 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	150 ms	57428 KB	Correct.
2	Correct	128 ms	24552 KB	Correct.
3	Correct	85 ms	30800 KB	Correct.
4	Correct	136 ms	32744 KB	Correct.
5	Correct	65 ms	30044 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	32840 KB	Correct.
2	Correct	25 ms	30808 KB	Correct.
3	Correct	30 ms	24668 KB	Correct.
4	Correct	38 ms	31580 KB	Correct.
5	Correct	34 ms	30040 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	30808 KB	Correct.
2	Correct	24 ms	30812 KB	Correct.
3	Correct	49 ms	70748 KB	Correct.
4	Correct	17 ms	34140 KB	Correct.
5	Correct	22 ms	32092 KB	Correct.
6	Correct	20 ms	26712 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	129 ms	24584 KB	Correct.
2	Correct	31 ms	31068 KB	Correct.
3	Correct	479 ms	81860 KB	Correct.
4	Correct	361 ms	43600 KB	Correct.
5	Correct	721 ms	54356 KB	Correct.
6	Correct	385 ms	40572 KB	Correct.
7	Correct	311 ms	42840 KB	Correct.
8	Correct	252 ms	32036 KB	Correct.
9	Correct	94 ms	30792 KB	Correct.
10	Correct	119 ms	32808 KB	Correct.
11	Correct	199 ms	30916 KB	Correct.
12	Correct	103 ms	24656 KB	Correct.
13	Correct	126 ms	24664 KB	Correct.
14	Correct	327 ms	50768 KB	Correct.
15	Correct	277 ms	36944 KB	Correct.
16	Correct	105 ms	30804 KB	Correct.
17	Correct	128 ms	26740 KB	Correct.
18	Correct	129 ms	26716 KB	Correct.
19	Correct	316 ms	30784 KB	Correct.
20	Correct	15 ms	30040 KB	Correct.
21	Correct	17 ms	30732 KB	Correct.
22	Correct	26 ms	24924 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	190 ms	32708 KB	Correct.
2	Correct	42 ms	31188 KB	Correct.
3	Correct	326 ms	85328 KB	Correct.
4	Correct	311 ms	35664 KB	Correct.
5	Correct	1581 ms	54596 KB	Correct.
6	Correct	822 ms	40528 KB	Correct.
7	Correct	564 ms	51536 KB	Correct.
8	Correct	234 ms	31144 KB	Correct.
9	Correct	153 ms	32844 KB	Correct.
10	Correct	159 ms	30812 KB	Correct.
11	Correct	139 ms	32372 KB	Correct.
12	Correct	170 ms	24656 KB	Correct.
13	Correct	168 ms	30816 KB	Correct.
14	Correct	1420 ms	49736 KB	Correct.
15	Correct	968 ms	52228 KB	Correct.
16	Correct	486 ms	36176 KB	Correct.
17	Correct	258 ms	32080 KB	Correct.
18	Correct	170 ms	32832 KB	Correct.
19	Correct	187 ms	26704 KB	Correct.
20	Correct	177 ms	30804 KB	Correct.
21	Correct	518 ms	30792 KB	Correct.
22	Correct	14 ms	25948 KB	Correct.
23	Correct	14 ms	24608 KB	Correct.
24	Correct	51 ms	24924 KB	Correct.

Submission #1071959

Compilation message