oj.uz

Submission #313922

# Submission time Handle Problem Language Result Execution time Memory
313922 2020-10-17T10:03:24 Z srvlt Stations (IOI20_stations) C++17
100 / 100
 940 ms 1048 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define SZ(x) (int)(x).size()
#define all(x) begin(x), end(x)

const int n0 = 1003;
int T, d[n0];
vector <int> g[n0], ind;
void dfs(int v, int p) {
	if (!d[v]) ind[v] = T++;
	for (int to : g[v]) {
		if (to == p) continue;
		d[to] = d[v] ^ 1;
		dfs(to, v);
	}
	if (d[v]) ind[v] = T++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	T = 0, memset(& d, 0, sizeof(d));
	ind = vector <int>(n, 0);
	for (int i = 0; i < n; i++) g[i].clear();
	for (int i = 0; i < SZ(u); i++)
		g[u[i]].pb(v[i]), g[v[i]].pb(u[i]);
	dfs(0, 0);
	//cerr << "ind\n";
	//for (int i = 0; i < n; i++) cerr << ind[i] << ' ';
	//cerr << '\n';
	return ind;
}

int find_next_station(int s, int t, vector<int> c) {
	//cerr << "s t " << s << ' ' << t << '\n';
	//cerr << "c\n";
	//for (int i : c) cerr << i << ' ';
	//cerr << '\n';
	
	if (c[0] > s) {
		int last = s + 1;
		for (int i = 0; i < SZ(c) - 1; i++) {
			if (t >= last && t <= c[i]) {
				//cerr << "ans " << c[i] << '\n';
				return c[i];
			}
			last = c[i] + 1;
		}
		//cerr << "ans " << c.back() << '\n';
		return c.back();
	}	else {
		int last = s - 1;
		for (int i = SZ(c) - 1; i > 0; i--) {
			if (t >= c[i] && t <= last) {
				//cerr << "ans " << c[i] << '\n';
				return c[i];
			}
			last = c[i] - 1;
		}
		//cerr << "ans " << c.back() << '\n';
		return c[0];
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 1024 KB Output is correct
2 Correct 450 ms 1024 KB Output is correct
3 Correct 860 ms 872 KB Output is correct
4 Correct 640 ms 868 KB Output is correct
5 Correct 564 ms 872 KB Output is correct
6 Correct 462 ms 772 KB Output is correct
7 Correct 447 ms 768 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 5 ms 672 KB Output is correct
10 Correct 1 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 804 KB Output is correct
2 Correct 526 ms 816 KB Output is correct
3 Correct 843 ms 872 KB Output is correct
4 Correct 658 ms 768 KB Output is correct
5 Correct 588 ms 784 KB Output is correct
6 Correct 463 ms 824 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 768 KB Output is correct
2 Correct 449 ms 1012 KB Output is correct
3 Correct 897 ms 872 KB Output is correct
4 Correct 655 ms 876 KB Output is correct
5 Correct 573 ms 1024 KB Output is correct
6 Correct 452 ms 776 KB Output is correct
7 Correct 477 ms 796 KB Output is correct
8 Correct 3 ms 880 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 2 ms 868 KB Output is correct
11 Correct 578 ms 768 KB Output is correct
12 Correct 487 ms 820 KB Output is correct
13 Correct 477 ms 896 KB Output is correct
14 Correct 480 ms 768 KB Output is correct
15 Correct 58 ms 768 KB Output is correct
16 Correct 64 ms 828 KB Output is correct
17 Correct 104 ms 928 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 838 ms 896 KB Output is correct
2 Correct 677 ms 768 KB Output is correct
3 Correct 591 ms 768 KB Output is correct
4 Correct 3 ms 868 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 590 ms 768 KB Output is correct
8 Correct 940 ms 768 KB Output is correct
9 Correct 710 ms 768 KB Output is correct
10 Correct 618 ms 768 KB Output is correct
11 Correct 6 ms 768 KB Output is correct
12 Correct 6 ms 768 KB Output is correct
13 Correct 4 ms 884 KB Output is correct
14 Correct 4 ms 872 KB Output is correct
15 Correct 2 ms 768 KB Output is correct
16 Correct 495 ms 768 KB Output is correct
17 Correct 492 ms 880 KB Output is correct
18 Correct 523 ms 1016 KB Output is correct
19 Correct 525 ms 876 KB Output is correct
20 Correct 533 ms 880 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 1028 KB Output is correct
2 Correct 462 ms 1024 KB Output is correct
3 Correct 879 ms 1040 KB Output is correct
4 Correct 660 ms 876 KB Output is correct
5 Correct 602 ms 768 KB Output is correct
6 Correct 464 ms 768 KB Output is correct
7 Correct 453 ms 804 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 2 ms 1024 KB Output is correct
11 Correct 472 ms 792 KB Output is correct
12 Correct 554 ms 816 KB Output is correct
13 Correct 860 ms 768 KB Output is correct
14 Correct 657 ms 872 KB Output is correct
15 Correct 575 ms 868 KB Output is correct
16 Correct 451 ms 824 KB Output is correct
17 Correct 590 ms 780 KB Output is correct
18 Correct 438 ms 788 KB Output is correct
19 Correct 461 ms 888 KB Output is correct
20 Correct 424 ms 816 KB Output is correct
21 Correct 59 ms 864 KB Output is correct
22 Correct 78 ms 768 KB Output is correct
23 Correct 111 ms 804 KB Output is correct
24 Correct 6 ms 868 KB Output is correct
25 Correct 6 ms 876 KB Output is correct
26 Correct 5 ms 768 KB Output is correct
27 Correct 3 ms 896 KB Output is correct
28 Correct 2 ms 880 KB Output is correct
29 Correct 633 ms 1048 KB Output is correct
30 Correct 502 ms 768 KB Output is correct
31 Correct 536 ms 876 KB Output is correct
32 Correct 525 ms 768 KB Output is correct
33 Correct 533 ms 768 KB Output is correct
34 Correct 326 ms 1024 KB Output is correct
35 Correct 460 ms 1016 KB Output is correct
36 Correct 471 ms 780 KB Output is correct
37 Correct 477 ms 968 KB Output is correct
38 Correct 496 ms 888 KB Output is correct
39 Correct 449 ms 768 KB Output is correct
40 Correct 486 ms 768 KB Output is correct
41 Correct 481 ms 888 KB Output is correct
42 Correct 64 ms 816 KB Output is correct
43 Correct 105 ms 940 KB Output is correct
44 Correct 142 ms 916 KB Output is correct
45 Correct 162 ms 768 KB Output is correct
46 Correct 312 ms 768 KB Output is correct
47 Correct 314 ms 1040 KB Output is correct
48 Correct 66 ms 1028 KB Output is correct
49 Correct 63 ms 1024 KB Output is correct