oj.uz

Submission #348370

# Submission time Handle Problem Language Result Execution time Memory
348370 2021-01-14T19:31:51 Z dennisstar Stations (IOI20_stations) C++17
100 / 100
 1180 ms 1248 KB 
#include <bits/stdc++.h>
#include "stations.h"

using namespace std;

const int MX = 1e3 + 5;

vector<int> L, adj[MX];
int O;

void dfs(int n, int p, int d) {
	if (d&1) L[n]=O++;
	for (auto &i:adj[n]) if (i!=p) dfs(i, n, d+1);
	if ((d-1)&1) L[n]=O++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	O=0;
	for (int i=0; i<n; i++) adj[i].clear();
	L.resize(n);
	for (int i=0; i<n-1; i++)
		adj[u[i]].emplace_back(v[i]),
		adj[v[i]].emplace_back(u[i]);
	dfs(0, -1, 1);
	return L;
}

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 1076 KB Output is correct
2 Correct 562 ms 864 KB Output is correct
3 Correct 996 ms 736 KB Output is correct
4 Correct 745 ms 896 KB Output is correct
5 Correct 751 ms 1208 KB Output is correct
6 Correct 509 ms 1084 KB Output is correct
7 Correct 560 ms 1112 KB Output is correct
8 Correct 3 ms 952 KB Output is correct
9 Correct 5 ms 960 KB Output is correct
10 Correct 2 ms 980 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 736 KB Output is correct
2 Correct 668 ms 736 KB Output is correct
3 Correct 1124 ms 992 KB Output is correct
4 Correct 866 ms 952 KB Output is correct
5 Correct 809 ms 952 KB Output is correct
6 Correct 548 ms 864 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 1064 KB Output is correct
2 Correct 507 ms 1068 KB Output is correct
3 Correct 1180 ms 824 KB Output is correct
4 Correct 717 ms 952 KB Output is correct
5 Correct 690 ms 992 KB Output is correct
6 Correct 440 ms 1084 KB Output is correct
7 Correct 524 ms 1248 KB Output is correct
8 Correct 3 ms 952 KB Output is correct
9 Correct 5 ms 736 KB Output is correct
10 Correct 1 ms 736 KB Output is correct
11 Correct 696 ms 864 KB Output is correct
12 Correct 551 ms 1120 KB Output is correct
13 Correct 518 ms 1088 KB Output is correct
14 Correct 439 ms 736 KB Output is correct
15 Correct 66 ms 864 KB Output is correct
16 Correct 77 ms 916 KB Output is correct
17 Correct 104 ms 864 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 991 ms 864 KB Output is correct
2 Correct 904 ms 952 KB Output is correct
3 Correct 684 ms 952 KB Output is correct
4 Correct 3 ms 960 KB Output is correct
5 Correct 5 ms 736 KB Output is correct
6 Correct 1 ms 952 KB Output is correct
7 Correct 798 ms 736 KB Output is correct
8 Correct 982 ms 952 KB Output is correct
9 Correct 705 ms 952 KB Output is correct
10 Correct 624 ms 952 KB Output is correct
11 Correct 6 ms 864 KB Output is correct
12 Correct 7 ms 864 KB Output is correct
13 Correct 6 ms 960 KB Output is correct
14 Correct 3 ms 952 KB Output is correct
15 Correct 2 ms 960 KB Output is correct
16 Correct 599 ms 864 KB Output is correct
17 Correct 549 ms 952 KB Output is correct
18 Correct 569 ms 1108 KB Output is correct
19 Correct 665 ms 864 KB Output is correct
20 Correct 586 ms 864 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 1068 KB Output is correct
2 Correct 479 ms 1204 KB Output is correct
3 Correct 998 ms 864 KB Output is correct
4 Correct 751 ms 864 KB Output is correct
5 Correct 598 ms 864 KB Output is correct
6 Correct 473 ms 1084 KB Output is correct
7 Correct 558 ms 888 KB Output is correct
8 Correct 3 ms 960 KB Output is correct
9 Correct 4 ms 864 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 514 ms 880 KB Output is correct
12 Correct 606 ms 736 KB Output is correct
13 Correct 980 ms 1208 KB Output is correct
14 Correct 746 ms 1080 KB Output is correct
15 Correct 657 ms 1248 KB Output is correct
16 Correct 559 ms 864 KB Output is correct
17 Correct 584 ms 992 KB Output is correct
18 Correct 607 ms 1004 KB Output is correct
19 Correct 579 ms 1084 KB Output is correct
20 Correct 541 ms 864 KB Output is correct
21 Correct 51 ms 864 KB Output is correct
22 Correct 90 ms 908 KB Output is correct
23 Correct 122 ms 864 KB Output is correct
24 Correct 6 ms 736 KB Output is correct
25 Correct 5 ms 736 KB Output is correct
26 Correct 6 ms 884 KB Output is correct
27 Correct 5 ms 736 KB Output is correct
28 Correct 2 ms 736 KB Output is correct
29 Correct 706 ms 768 KB Output is correct
30 Correct 628 ms 952 KB Output is correct
31 Correct 539 ms 864 KB Output is correct
32 Correct 684 ms 736 KB Output is correct
33 Correct 664 ms 952 KB Output is correct
34 Correct 387 ms 1080 KB Output is correct
35 Correct 422 ms 1064 KB Output is correct
36 Correct 461 ms 992 KB Output is correct
37 Correct 538 ms 1004 KB Output is correct
38 Correct 496 ms 1004 KB Output is correct
39 Correct 422 ms 1100 KB Output is correct
40 Correct 423 ms 1100 KB Output is correct
41 Correct 557 ms 1008 KB Output is correct
42 Correct 78 ms 900 KB Output is correct
43 Correct 137 ms 736 KB Output is correct
44 Correct 202 ms 864 KB Output is correct
45 Correct 138 ms 872 KB Output is correct
46 Correct 413 ms 1016 KB Output is correct
47 Correct 427 ms 864 KB Output is correct
48 Correct 63 ms 1100 KB Output is correct
49 Correct 56 ms 992 KB Output is correct