Submission #996747

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
996747	2024-06-11T06:46:44 Z	phoenix	Stations (IOI20_stations)	C++17	100 / 100	663 ms	1044 KB

stations

#include "stations.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>

using namespace std;

const int N = 1010;

int T;
int tin[N];
int tout[N];
vector<int> g[N];

void precalc(int s, int p) {
	tin[s] = T++;
	for (int to : g[s]) if (to != p)
		precalc(to, s);
	tout[s] = T++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	T = 0;
	for (int i = 0; i < n; i++) {
		g[i].clear();
	}
	for (int i = 0; i < n - 1; i++) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}	
	vector<int> labels(n);
	precalc(0, 0);
	for (int i = 0; i < n; i++)
		if (tin[i] & 1) 
			labels[i] = tout[i];
		else 
			labels[i] = tin[i];
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](int x, int y) {
		return labels[x] < labels[y];
	});	
	for (int i = 0; i < n; i++) 
		labels[ord[i]] = i;
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	if ((int)c.size() == 1) 
		return c[0];
	int m = (int)c.size();
	sort(c.begin(), c.end());

	if (!s) {
		int prev = s;
		for (int i = 0; i < m; i++) {
			int l = prev + 1; 
			int r = c[i];
			prev = c[i];
			if (l <= t && t <= r)
				return c[i];
		}
	}

	if (s < c[0]) {
		int prev = s + 1;
		for (int i = 0; i < m - 1; i++) {
			int l = prev; 
			int r = c[i];
			prev = c[i] + 1;
			if (l <= t && t <= r)
				return c[i];
		}
		return c.back(	);
	} 
	int prev = s - 1;
	for (int i = m - 1; i >= 1; i--) {
		int l = c[i];
		int r = prev;
		prev = c[i] - 1;
		if (l <= t && t <= r) 
			return c[i];
	}
	return c[0];
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	361 ms	684 KB	Output is correct
2	Correct	311 ms	684 KB	Output is correct
3	Correct	593 ms	684 KB	Output is correct
4	Correct	509 ms	684 KB	Output is correct
5	Correct	410 ms	688 KB	Output is correct
6	Correct	288 ms	684 KB	Output is correct
7	Correct	315 ms	684 KB	Output is correct
8	Correct	1 ms	768 KB	Output is correct
9	Correct	2 ms	776 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	333 ms	684 KB	Output is correct
2	Correct	380 ms	684 KB	Output is correct
3	Correct	651 ms	684 KB	Output is correct
4	Correct	457 ms	684 KB	Output is correct
5	Correct	402 ms	684 KB	Output is correct
6	Correct	325 ms	684 KB	Output is correct

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	417 ms	684 KB	Output is correct
2	Correct	296 ms	684 KB	Output is correct
3	Correct	658 ms	684 KB	Output is correct
4	Correct	456 ms	684 KB	Output is correct
5	Correct	377 ms	684 KB	Output is correct
6	Correct	322 ms	684 KB	Output is correct
7	Correct	317 ms	684 KB	Output is correct
8	Correct	1 ms	764 KB	Output is correct
9	Correct	2 ms	764 KB	Output is correct
10	Correct	0 ms	768 KB	Output is correct
11	Correct	393 ms	684 KB	Output is correct
12	Correct	321 ms	932 KB	Output is correct
13	Correct	307 ms	788 KB	Output is correct
14	Correct	280 ms	684 KB	Output is correct
15	Correct	31 ms	768 KB	Output is correct
16	Correct	62 ms	684 KB	Output is correct
17	Correct	56 ms	684 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	626 ms	684 KB	Output is correct
2	Correct	406 ms	684 KB	Output is correct
3	Correct	380 ms	684 KB	Output is correct
4	Correct	1 ms	776 KB	Output is correct
5	Correct	2 ms	768 KB	Output is correct
6	Correct	0 ms	776 KB	Output is correct
7	Correct	419 ms	684 KB	Output is correct
8	Correct	607 ms	792 KB	Output is correct
9	Correct	448 ms	684 KB	Output is correct
10	Correct	407 ms	684 KB	Output is correct
11	Correct	2 ms	768 KB	Output is correct
12	Correct	2 ms	776 KB	Output is correct
13	Correct	2 ms	768 KB	Output is correct
14	Correct	2 ms	768 KB	Output is correct
15	Correct	1 ms	764 KB	Output is correct
16	Correct	330 ms	792 KB	Output is correct
17	Correct	342 ms	684 KB	Output is correct
18	Correct	363 ms	684 KB	Output is correct
19	Correct	336 ms	684 KB	Output is correct
20	Correct	322 ms	684 KB	Output is correct

Subtask #5
61.0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	379 ms	684 KB	Output is correct
2	Correct	316 ms	684 KB	Output is correct
3	Correct	663 ms	684 KB	Output is correct
4	Correct	441 ms	680 KB	Output is correct
5	Correct	390 ms	680 KB	Output is correct
6	Correct	309 ms	684 KB	Output is correct
7	Correct	326 ms	684 KB	Output is correct
8	Correct	2 ms	768 KB	Output is correct
9	Correct	2 ms	772 KB	Output is correct
10	Correct	0 ms	776 KB	Output is correct
11	Correct	308 ms	684 KB	Output is correct
12	Correct	345 ms	684 KB	Output is correct
13	Correct	572 ms	688 KB	Output is correct
14	Correct	460 ms	684 KB	Output is correct
15	Correct	372 ms	684 KB	Output is correct
16	Correct	299 ms	684 KB	Output is correct
17	Correct	401 ms	684 KB	Output is correct
18	Correct	308 ms	944 KB	Output is correct
19	Correct	304 ms	932 KB	Output is correct
20	Correct	346 ms	684 KB	Output is correct
21	Correct	29 ms	768 KB	Output is correct
22	Correct	40 ms	712 KB	Output is correct
23	Correct	56 ms	684 KB	Output is correct
24	Correct	2 ms	768 KB	Output is correct
25	Correct	2 ms	768 KB	Output is correct
26	Correct	2 ms	776 KB	Output is correct
27	Correct	1 ms	776 KB	Output is correct
28	Correct	1 ms	768 KB	Output is correct
29	Correct	359 ms	684 KB	Output is correct
30	Correct	364 ms	688 KB	Output is correct
31	Correct	356 ms	684 KB	Output is correct
32	Correct	368 ms	684 KB	Output is correct
33	Correct	340 ms	684 KB	Output is correct
34	Correct	237 ms	684 KB	Output is correct
35	Correct	306 ms	788 KB	Output is correct
36	Correct	325 ms	932 KB	Output is correct
37	Correct	289 ms	1044 KB	Output is correct
38	Correct	316 ms	932 KB	Output is correct
39	Correct	319 ms	808 KB	Output is correct
40	Correct	284 ms	792 KB	Output is correct
41	Correct	293 ms	800 KB	Output is correct
42	Correct	33 ms	704 KB	Output is correct
43	Correct	57 ms	728 KB	Output is correct
44	Correct	81 ms	684 KB	Output is correct
45	Correct	110 ms	688 KB	Output is correct
46	Correct	202 ms	684 KB	Output is correct
47	Correct	221 ms	684 KB	Output is correct
48	Correct	46 ms	848 KB	Output is correct
49	Correct	32 ms	876 KB	Output is correct

Submission #996747

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 8.0 / 8.0

Subtask #3 16.0 / 16.0

Subtask #4 10.0 / 10.0

Subtask #5 61.0 / 61.0

Subtask #1
5.0 / 5.0

Subtask #2
8.0 / 8.0

Subtask #3
16.0 / 16.0

Subtask #4
10.0 / 10.0

Subtask #5
61.0 / 61.0