oj.uz

Submission #421629

# Submission time Handle Problem Language Result Execution time Memory
421629 2021-06-09T10:13:47 Z ja_kingy Stations (IOI20_stations) C++14
100 / 100
 1240 ms 780 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

int cnt;
vector<int> adj[1000], labels;
void dfs(int u, int p, bool tp) {
	if (!tp) labels[u] = cnt++;
	for (int v: adj[u]) if (v != p) {
		dfs(v, u, 1-tp);
	}
	if (tp) labels[u] = cnt++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	cnt = 0;
	labels.resize(n);
	for (int i = 0; i < n; ++i) adj[i].clear();
	for (int i = 0; i < n-1; ++i) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	dfs(0, 0, 0);
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	sort(c.begin(), c.end());
	if (s <= c.front()) {
		if (t < s) return c.back();
		auto it = lower_bound(c.begin(), c.end(), t);
		if (it == c.end()) return c.back();
		else return *it;
	} else {
		if (t > s) return c.front();
		auto it = upper_bound(c.begin(), c.end(), t);
		if (it == c.begin()) return *it;
		else return *(--it);
	}
	return c[0];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 528 KB Output is correct
2 Correct 579 ms 632 KB Output is correct
3 Correct 1240 ms 400 KB Output is correct
4 Correct 839 ms 512 KB Output is correct
5 Correct 732 ms 536 KB Output is correct
6 Correct 552 ms 504 KB Output is correct
7 Correct 645 ms 512 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 2 ms 480 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 512 KB Output is correct
2 Correct 712 ms 512 KB Output is correct
3 Correct 1121 ms 564 KB Output is correct
4 Correct 872 ms 500 KB Output is correct
5 Correct 835 ms 556 KB Output is correct
6 Correct 537 ms 564 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 652 KB Output is correct
2 Correct 646 ms 656 KB Output is correct
3 Correct 984 ms 568 KB Output is correct
4 Correct 936 ms 584 KB Output is correct
5 Correct 822 ms 512 KB Output is correct
6 Correct 651 ms 736 KB Output is correct
7 Correct 574 ms 580 KB Output is correct
8 Correct 4 ms 540 KB Output is correct
9 Correct 5 ms 540 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 558 ms 508 KB Output is correct
12 Correct 554 ms 648 KB Output is correct
13 Correct 620 ms 656 KB Output is correct
14 Correct 462 ms 528 KB Output is correct
15 Correct 79 ms 400 KB Output is correct
16 Correct 65 ms 528 KB Output is correct
17 Correct 125 ms 528 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1103 ms 400 KB Output is correct
2 Correct 729 ms 400 KB Output is correct
3 Correct 824 ms 516 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 1 ms 448 KB Output is correct
7 Correct 718 ms 508 KB Output is correct
8 Correct 1013 ms 400 KB Output is correct
9 Correct 854 ms 508 KB Output is correct
10 Correct 816 ms 400 KB Output is correct
11 Correct 7 ms 468 KB Output is correct
12 Correct 5 ms 468 KB Output is correct
13 Correct 6 ms 476 KB Output is correct
14 Correct 4 ms 448 KB Output is correct
15 Correct 2 ms 488 KB Output is correct
16 Correct 696 ms 400 KB Output is correct
17 Correct 605 ms 400 KB Output is correct
18 Correct 699 ms 492 KB Output is correct
19 Correct 644 ms 400 KB Output is correct
20 Correct 552 ms 512 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 624 KB Output is correct
2 Correct 627 ms 616 KB Output is correct
3 Correct 950 ms 516 KB Output is correct
4 Correct 786 ms 512 KB Output is correct
5 Correct 694 ms 512 KB Output is correct
6 Correct 564 ms 508 KB Output is correct
7 Correct 480 ms 512 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 528 ms 588 KB Output is correct
12 Correct 714 ms 508 KB Output is correct
13 Correct 1113 ms 400 KB Output is correct
14 Correct 753 ms 512 KB Output is correct
15 Correct 782 ms 400 KB Output is correct
16 Correct 543 ms 532 KB Output is correct
17 Correct 811 ms 400 KB Output is correct
18 Correct 491 ms 612 KB Output is correct
19 Correct 559 ms 636 KB Output is correct
20 Correct 512 ms 488 KB Output is correct
21 Correct 68 ms 400 KB Output is correct
22 Correct 94 ms 528 KB Output is correct
23 Correct 104 ms 556 KB Output is correct
24 Correct 6 ms 468 KB Output is correct
25 Correct 6 ms 468 KB Output is correct
26 Correct 5 ms 468 KB Output is correct
27 Correct 3 ms 468 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 635 ms 512 KB Output is correct
30 Correct 644 ms 400 KB Output is correct
31 Correct 646 ms 588 KB Output is correct
32 Correct 582 ms 544 KB Output is correct
33 Correct 553 ms 400 KB Output is correct
34 Correct 359 ms 640 KB Output is correct
35 Correct 474 ms 656 KB Output is correct
36 Correct 555 ms 740 KB Output is correct
37 Correct 579 ms 640 KB Output is correct
38 Correct 496 ms 612 KB Output is correct
39 Correct 471 ms 776 KB Output is correct
40 Correct 484 ms 780 KB Output is correct
41 Correct 553 ms 624 KB Output is correct
42 Correct 76 ms 668 KB Output is correct
43 Correct 127 ms 588 KB Output is correct
44 Correct 140 ms 528 KB Output is correct
45 Correct 168 ms 512 KB Output is correct
46 Correct 416 ms 528 KB Output is correct
47 Correct 334 ms 508 KB Output is correct
48 Correct 76 ms 656 KB Output is correct
49 Correct 75 ms 676 KB Output is correct