oj.uz

Submission #959045

# Submission time Handle Problem Language Result Execution time Memory
959045 2024-04-07T12:18:40 Z The_Samurai Stations (IOI20_stations) C++17
52.3205 / 100
 600 ms 1512 KB 
#include "stations.h"
#include "bits/stdc++.h"
using namespace std;

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	vector<vector<int>> adj(n);
	vector<bool> vis(n);
	for (int i = 0; i < n - 1; i++) {
		adj[u[i]].emplace_back(v[i]);
		adj[v[i]].emplace_back(u[i]);
	}
	int z = 0;
	vector<int> tin(n), tout(n), ans(n);
	auto dfs = [&](auto &dfs, int u) -> void {
		tin[u] = tout[u] = z++;
		vis[u] = true;
		for (int v: adj[u]) {
			if (vis[v]) continue;
			dfs(dfs, v);
			tout[u] = tout[v];
		}
	};
	dfs(dfs, 0);
	for (int i = 0; i < n; i++) ans[i] = tin[i] * 1000 + tout[i];
	// cout << '\t';
	// for (int i = 0; i < n; i++) cout << tin[i] << ' ';
	// cout << endl;
	// for (int i = 0; i < n - 1; i++) cout << tin[u[i]] << ' ' << tin[v[i]] << endl;
	return ans;
}

bool is_par(int v1, int v2) {
	int tin1 = v1 / 1000, tout1 = v1 % 1000;
	int tin2 = v2 / 1000, tout2 = v2 % 1000;
	return tin1 <= tin2 and tout2 <= tout1;
}

int find_next_station(int s, int t, std::vector<int> c) {
	// cout << '\t' << s << ' ' << t << endl;
	// cout << '\t';
	// for (int x: c) cout << x << ' ';
	// cout << endl;
	for (int u: c) {
		if (is_par(s, u) and is_par(u, t)) return u;
	}
	for (int u: c) {
		if (is_par(u, s)) return u;
	}
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
   49 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 544 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=6009
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 768 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1511
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 888 KB Output is correct
2 Correct 291 ms 1056 KB Output is correct
3 Correct 539 ms 1020 KB Output is correct
4 Correct 418 ms 940 KB Output is correct
5 Correct 359 ms 684 KB Output is correct
6 Correct 298 ms 888 KB Output is correct
7 Correct 291 ms 684 KB Output is correct
8 Correct 2 ms 764 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 390 ms 684 KB Output is correct
12 Correct 350 ms 1212 KB Output is correct
13 Correct 319 ms 1396 KB Output is correct
14 Correct 276 ms 684 KB Output is correct
15 Correct 38 ms 764 KB Output is correct
16 Correct 40 ms 912 KB Output is correct
17 Correct 59 ms 928 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 684 KB Output is correct
2 Correct 450 ms 684 KB Output is correct
3 Correct 371 ms 684 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 415 ms 684 KB Output is correct
8 Correct 582 ms 940 KB Output is correct
9 Correct 466 ms 684 KB Output is correct
10 Correct 400 ms 684 KB Output is correct
11 Correct 3 ms 764 KB Output is correct
12 Correct 2 ms 768 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 0 ms 764 KB Output is correct
16 Correct 331 ms 940 KB Output is correct
17 Correct 311 ms 684 KB Output is correct
18 Correct 313 ms 688 KB Output is correct
19 Correct 317 ms 684 KB Output is correct
20 Correct 327 ms 684 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 349 ms 1148 KB Partially correct
2 Partially correct 300 ms 1052 KB Partially correct
3 Partially correct 566 ms 684 KB Partially correct
4 Partially correct 439 ms 684 KB Partially correct
5 Partially correct 379 ms 684 KB Partially correct
6 Partially correct 316 ms 1136 KB Partially correct
7 Partially correct 313 ms 944 KB Partially correct
8 Partially correct 1 ms 768 KB Partially correct
9 Partially correct 3 ms 1020 KB Partially correct
10 Partially correct 0 ms 768 KB Partially correct
11 Partially correct 297 ms 864 KB Partially correct
12 Partially correct 369 ms 1000 KB Partially correct
13 Partially correct 600 ms 684 KB Partially correct
14 Partially correct 443 ms 944 KB Partially correct
15 Partially correct 448 ms 684 KB Partially correct
16 Partially correct 285 ms 684 KB Partially correct
17 Partially correct 388 ms 940 KB Partially correct
18 Partially correct 303 ms 976 KB Partially correct
19 Partially correct 304 ms 968 KB Partially correct
20 Partially correct 248 ms 684 KB Partially correct
21 Partially correct 37 ms 768 KB Partially correct
22 Partially correct 46 ms 1088 KB Partially correct
23 Partially correct 61 ms 1036 KB Partially correct
24 Partially correct 4 ms 768 KB Partially correct
25 Partially correct 4 ms 768 KB Partially correct
26 Partially correct 2 ms 768 KB Partially correct
27 Partially correct 3 ms 768 KB Partially correct
28 Partially correct 1 ms 768 KB Partially correct
29 Partially correct 318 ms 684 KB Partially correct
30 Partially correct 302 ms 684 KB Partially correct
31 Partially correct 353 ms 772 KB Partially correct
32 Partially correct 337 ms 684 KB Partially correct
33 Partially correct 387 ms 684 KB Partially correct
34 Partially correct 236 ms 892 KB Partially correct
35 Partially correct 276 ms 1152 KB Partially correct
36 Partially correct 284 ms 1220 KB Partially correct
37 Partially correct 316 ms 1132 KB Partially correct
38 Partially correct 286 ms 956 KB Partially correct
39 Partially correct 293 ms 1300 KB Partially correct
40 Partially correct 277 ms 1140 KB Partially correct
41 Partially correct 303 ms 1124 KB Partially correct
42 Partially correct 36 ms 932 KB Partially correct
43 Partially correct 59 ms 1120 KB Partially correct
44 Partially correct 92 ms 860 KB Partially correct
45 Partially correct 97 ms 868 KB Partially correct
46 Partially correct 191 ms 844 KB Partially correct
47 Partially correct 209 ms 872 KB Partially correct
48 Partially correct 32 ms 1208 KB Partially correct
49 Partially correct 36 ms 1512 KB Partially correct