oj.uz

Submission #621859

# Submission time Handle Problem Language Result Execution time Memory
621859 2022-08-04T02:45:56 Z 8e7 Stations (IOI20_stations) C++17
100 / 100
 1079 ms 860 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000
#define pii pair<int, int>
#define ff first
#define ss second
#include "stations.h"
const int mul = 501;

vector<int> adj[maxn];
int mark[maxn];
int ti;
int dep[maxn];
void dfs(int n, int par, int d) {
	dep[n] = d;
	if (d % 2 == 0) mark[n] = ti++;
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n, d+1);
		}
	}
	if (d % 2) mark[n] = ti++;
}
std::vector<int> label(int n, int LIM, std::vector<int> U, std::vector<int> V) {
	vector<int> ret(n);
	for (int i = 0;i < n;i++) {
		adj[i].clear();
		mark[i] = 0;
	}
	ti = 0;

	for (int i = 0;i < n - 1;i++) {
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	dfs(0, -1, 0);
	for (int i = 0;i < n;i++) ret[i] = mark[i];
	return ret;
}

const int inf = 1e9;
int find_next_station(int s, int t, std::vector<int> c) {
	sort(c.begin(), c.end());
	bool in = 1;		
	for (int v:c) {
		if (s > v) in = 0;
	}
	if (in) {
		if (t < s) return c.back();
		for (int v:c) {
			if (t <= v) return v;
		}
		return c.back();
	} else {
		if (t > s) return c[0];
		for (int i = (int)c.size() - 1;i >= 0;i--) {
			int v = c[i];
			if (t >= v) return v;
		}
		return c[0];
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 748 KB Output is correct
2 Correct 502 ms 668 KB Output is correct
3 Correct 1053 ms 564 KB Output is correct
4 Correct 719 ms 420 KB Output is correct
5 Correct 608 ms 740 KB Output is correct
6 Correct 533 ms 532 KB Output is correct
7 Correct 441 ms 724 KB Output is correct
8 Correct 6 ms 640 KB Output is correct
9 Correct 5 ms 620 KB Output is correct
10 Correct 2 ms 536 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 536 KB Output is correct
2 Correct 543 ms 612 KB Output is correct
3 Correct 982 ms 512 KB Output is correct
4 Correct 604 ms 512 KB Output is correct
5 Correct 678 ms 416 KB Output is correct
6 Correct 542 ms 548 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 820 KB Output is correct
2 Correct 457 ms 696 KB Output is correct
3 Correct 897 ms 420 KB Output is correct
4 Correct 705 ms 512 KB Output is correct
5 Correct 610 ms 528 KB Output is correct
6 Correct 550 ms 832 KB Output is correct
7 Correct 431 ms 548 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 5 ms 492 KB Output is correct
10 Correct 2 ms 484 KB Output is correct
11 Correct 612 ms 420 KB Output is correct
12 Correct 516 ms 756 KB Output is correct
13 Correct 555 ms 716 KB Output is correct
14 Correct 501 ms 660 KB Output is correct
15 Correct 56 ms 548 KB Output is correct
16 Correct 61 ms 536 KB Output is correct
17 Correct 101 ms 720 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1079 ms 416 KB Output is correct
2 Correct 651 ms 528 KB Output is correct
3 Correct 661 ms 548 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 4 ms 500 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 537 ms 556 KB Output is correct
8 Correct 900 ms 596 KB Output is correct
9 Correct 670 ms 528 KB Output is correct
10 Correct 637 ms 548 KB Output is correct
11 Correct 6 ms 492 KB Output is correct
12 Correct 4 ms 492 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 4 ms 492 KB Output is correct
15 Correct 2 ms 572 KB Output is correct
16 Correct 465 ms 416 KB Output is correct
17 Correct 600 ms 484 KB Output is correct
18 Correct 476 ms 484 KB Output is correct
19 Correct 547 ms 532 KB Output is correct
20 Correct 590 ms 420 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 652 KB Output is correct
2 Correct 511 ms 692 KB Output is correct
3 Correct 840 ms 420 KB Output is correct
4 Correct 756 ms 528 KB Output is correct
5 Correct 510 ms 532 KB Output is correct
6 Correct 634 ms 652 KB Output is correct
7 Correct 477 ms 688 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 5 ms 556 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 486 ms 592 KB Output is correct
12 Correct 671 ms 668 KB Output is correct
13 Correct 1012 ms 548 KB Output is correct
14 Correct 744 ms 512 KB Output is correct
15 Correct 722 ms 416 KB Output is correct
16 Correct 507 ms 536 KB Output is correct
17 Correct 712 ms 536 KB Output is correct
18 Correct 566 ms 656 KB Output is correct
19 Correct 480 ms 756 KB Output is correct
20 Correct 492 ms 508 KB Output is correct
21 Correct 73 ms 548 KB Output is correct
22 Correct 64 ms 528 KB Output is correct
23 Correct 150 ms 544 KB Output is correct
24 Correct 4 ms 492 KB Output is correct
25 Correct 4 ms 508 KB Output is correct
26 Correct 6 ms 456 KB Output is correct
27 Correct 4 ms 612 KB Output is correct
28 Correct 3 ms 468 KB Output is correct
29 Correct 589 ms 512 KB Output is correct
30 Correct 677 ms 592 KB Output is correct
31 Correct 568 ms 516 KB Output is correct
32 Correct 592 ms 416 KB Output is correct
33 Correct 573 ms 416 KB Output is correct
34 Correct 373 ms 860 KB Output is correct
35 Correct 511 ms 752 KB Output is correct
36 Correct 492 ms 748 KB Output is correct
37 Correct 590 ms 696 KB Output is correct
38 Correct 478 ms 656 KB Output is correct
39 Correct 501 ms 724 KB Output is correct
40 Correct 586 ms 724 KB Output is correct
41 Correct 443 ms 684 KB Output is correct
42 Correct 99 ms 672 KB Output is correct
43 Correct 128 ms 672 KB Output is correct
44 Correct 156 ms 528 KB Output is correct
45 Correct 207 ms 588 KB Output is correct
46 Correct 389 ms 536 KB Output is correct
47 Correct 329 ms 532 KB Output is correct
48 Correct 52 ms 784 KB Output is correct
49 Correct 60 ms 724 KB Output is correct