oj.uz

Submission #838288

# Submission time Handle Problem Language Result Execution time Memory
838288 2023-08-26T12:59:04 Z puppy Stations (IOI20_stations) C++17
100 / 100
 678 ms 796 KB 
#include "stations.h"
#include <vector>
#include <functional>
#include <algorithm>
#include <iostream>
using namespace std;

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	vector<vector<int>> adj(n);
	for (int i = 0; i < n-1; i++) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	vector<int> id(n);
	int ord = 0;
	function<void(int, int, int)> dfs = [&](int v, int p, int depth)
	{
		if (depth % 2 == 0) id[v] = ord++;
		for (int i:adj[v]) {
			if (i != p) dfs(i, v, depth + 1);
		}
		if (depth % 2 == 1) id[v] = ord++;
	};
	dfs(0, -1, 0);
	return id;
}

int find_next_station(int s, int t, std::vector<int> c) {
	int parity = s > c[0];
	sort(c.begin(), c.end());
	if (s) {
		if (parity == 0) {
			if (t < s || c[c.size()-2] < t || c.size() == 1) return c.back();
		}
		else {
			if (t < c[1] || s < t || c.size() == 1) return c[0];
		}
	}
	if (parity == 0) {
		for (int i = 0; i < (int)c.size(); i++) {
			if (t <= c[i]) return c[i];
		}
	}
	else {
		for (int i = (int)c.size() - 1; i >= 0; i--) {
			if (t >= c[i]) return c[i];
		}
	}
}

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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 676 KB Output is correct
2 Correct 417 ms 744 KB Output is correct
3 Correct 598 ms 420 KB Output is correct
4 Correct 462 ms 492 KB Output is correct
5 Correct 523 ms 420 KB Output is correct
6 Correct 264 ms 664 KB Output is correct
7 Correct 324 ms 544 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 4 ms 500 KB Output is correct
10 Correct 0 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 596 KB Output is correct
2 Correct 442 ms 544 KB Output is correct
3 Correct 627 ms 420 KB Output is correct
4 Correct 491 ms 420 KB Output is correct
5 Correct 470 ms 540 KB Output is correct
6 Correct 300 ms 544 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 672 KB Output is correct
2 Correct 309 ms 676 KB Output is correct
3 Correct 653 ms 420 KB Output is correct
4 Correct 475 ms 420 KB Output is correct
5 Correct 480 ms 420 KB Output is correct
6 Correct 266 ms 796 KB Output is correct
7 Correct 237 ms 544 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 3 ms 500 KB Output is correct
10 Correct 0 ms 500 KB Output is correct
11 Correct 378 ms 420 KB Output is correct
12 Correct 269 ms 680 KB Output is correct
13 Correct 354 ms 748 KB Output is correct
14 Correct 302 ms 548 KB Output is correct
15 Correct 49 ms 492 KB Output is correct
16 Correct 39 ms 564 KB Output is correct
17 Correct 91 ms 548 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 420 KB Output is correct
2 Correct 474 ms 420 KB Output is correct
3 Correct 506 ms 416 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 0 ms 492 KB Output is correct
7 Correct 342 ms 420 KB Output is correct
8 Correct 632 ms 416 KB Output is correct
9 Correct 417 ms 416 KB Output is correct
10 Correct 432 ms 420 KB Output is correct
11 Correct 4 ms 500 KB Output is correct
12 Correct 4 ms 504 KB Output is correct
13 Correct 3 ms 492 KB Output is correct
14 Correct 2 ms 492 KB Output is correct
15 Correct 1 ms 496 KB Output is correct
16 Correct 457 ms 540 KB Output is correct
17 Correct 407 ms 420 KB Output is correct
18 Correct 481 ms 668 KB Output is correct
19 Correct 366 ms 416 KB Output is correct
20 Correct 391 ms 416 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 672 KB Output is correct
2 Correct 265 ms 544 KB Output is correct
3 Correct 506 ms 440 KB Output is correct
4 Correct 412 ms 420 KB Output is correct
5 Correct 390 ms 416 KB Output is correct
6 Correct 292 ms 676 KB Output is correct
7 Correct 312 ms 668 KB Output is correct
8 Correct 1 ms 500 KB Output is correct
9 Correct 3 ms 500 KB Output is correct
10 Correct 0 ms 500 KB Output is correct
11 Correct 282 ms 592 KB Output is correct
12 Correct 349 ms 544 KB Output is correct
13 Correct 530 ms 420 KB Output is correct
14 Correct 458 ms 464 KB Output is correct
15 Correct 419 ms 420 KB Output is correct
16 Correct 303 ms 668 KB Output is correct
17 Correct 407 ms 416 KB Output is correct
18 Correct 287 ms 544 KB Output is correct
19 Correct 315 ms 692 KB Output is correct
20 Correct 282 ms 548 KB Output is correct
21 Correct 37 ms 492 KB Output is correct
22 Correct 60 ms 572 KB Output is correct
23 Correct 70 ms 572 KB Output is correct
24 Correct 2 ms 492 KB Output is correct
25 Correct 3 ms 500 KB Output is correct
26 Correct 2 ms 492 KB Output is correct
27 Correct 2 ms 500 KB Output is correct
28 Correct 0 ms 492 KB Output is correct
29 Correct 318 ms 416 KB Output is correct
30 Correct 364 ms 420 KB Output is correct
31 Correct 347 ms 428 KB Output is correct
32 Correct 313 ms 416 KB Output is correct
33 Correct 336 ms 420 KB Output is correct
34 Correct 216 ms 672 KB Output is correct
35 Correct 296 ms 748 KB Output is correct
36 Correct 311 ms 676 KB Output is correct
37 Correct 369 ms 752 KB Output is correct
38 Correct 283 ms 640 KB Output is correct
39 Correct 421 ms 632 KB Output is correct
40 Correct 347 ms 668 KB Output is correct
41 Correct 257 ms 640 KB Output is correct
42 Correct 37 ms 604 KB Output is correct
43 Correct 88 ms 644 KB Output is correct
44 Correct 116 ms 696 KB Output is correct
45 Correct 144 ms 544 KB Output is correct
46 Correct 204 ms 548 KB Output is correct
47 Correct 229 ms 544 KB Output is correct
48 Correct 55 ms 740 KB Output is correct
49 Correct 38 ms 672 KB Output is correct