Submission #428516

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
428516	2021-06-15T12:29:48 Z	egekabas	Stations (IOI20_stations)	C++14	100 / 100	1119 ms	848 KB

stations

#include "stations.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
vector<int> g[1009];
vector<int> ans;
int curt = 0;
void dfs(int v, int prt, int depth){
	if(depth%2 == 0)
		ans[v] = curt++;
	for(auto u : g[v])
		if(u != prt)
			dfs(u, v, depth+1);
	if(depth%2 == 1)
		ans[v] = curt++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	ans = vector<int>(n);
	for(int i = 0; i < n; ++i)
		g[i].clear();
	for(int i = 0; i < n-1; ++i){
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}
	curt = 0;
	dfs(0, -1, 0);
	return ans;
}

int find_next_station(int s, int t, std::vector<int> c) {
	int smaller = 0;
	for(auto u : c)
		if(u < s)
			smaller = 1;
	if(smaller == 0){
		sort(all(c));
		if(t < s)
			return c.back();
		for(auto u : c)
			if(t <= u)
				return u;
		return c.back();
	}
	else{
		
		sort(all(c), greater<int>());
		if(t > s)
			return c.back();
		for(auto u : c)
			if(t >= u)
				return u;
		return c.back();
	}
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	805 ms	636 KB	Output is correct
2	Correct	641 ms	716 KB	Output is correct
3	Correct	964 ms	404 KB	Output is correct
4	Correct	933 ms	552 KB	Output is correct
5	Correct	692 ms	436 KB	Output is correct
6	Correct	540 ms	620 KB	Output is correct
7	Correct	654 ms	528 KB	Output is correct
8	Correct	3 ms	452 KB	Output is correct
9	Correct	8 ms	456 KB	Output is correct
10	Correct	3 ms	468 KB	Output is correct

Subtask #2

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	561 ms	516 KB	Output is correct
2	Correct	633 ms	524 KB	Output is correct
3	Correct	1085 ms	400 KB	Output is correct
4	Correct	899 ms	488 KB	Output is correct
5	Correct	738 ms	400 KB	Output is correct
6	Correct	524 ms	528 KB	Output is correct

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	813 ms	652 KB	Output is correct
2	Correct	544 ms	644 KB	Output is correct
3	Correct	1065 ms	400 KB	Output is correct
4	Correct	1099 ms	512 KB	Output is correct
5	Correct	757 ms	400 KB	Output is correct
6	Correct	486 ms	500 KB	Output is correct
7	Correct	706 ms	528 KB	Output is correct
8	Correct	3 ms	472 KB	Output is correct
9	Correct	7 ms	468 KB	Output is correct
10	Correct	5 ms	536 KB	Output is correct
11	Correct	710 ms	400 KB	Output is correct
12	Correct	456 ms	736 KB	Output is correct
13	Correct	692 ms	848 KB	Output is correct
14	Correct	503 ms	504 KB	Output is correct
15	Correct	77 ms	468 KB	Output is correct
16	Correct	68 ms	528 KB	Output is correct
17	Correct	168 ms	528 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1119 ms	400 KB	Output is correct
2	Correct	685 ms	400 KB	Output is correct
3	Correct	754 ms	400 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	6 ms	468 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	749 ms	400 KB	Output is correct
8	Correct	942 ms	400 KB	Output is correct
9	Correct	716 ms	400 KB	Output is correct
10	Correct	683 ms	400 KB	Output is correct
11	Correct	7 ms	468 KB	Output is correct
12	Correct	5 ms	476 KB	Output is correct
13	Correct	6 ms	476 KB	Output is correct
14	Correct	6 ms	468 KB	Output is correct
15	Correct	2 ms	464 KB	Output is correct
16	Correct	608 ms	472 KB	Output is correct
17	Correct	627 ms	400 KB	Output is correct
18	Correct	690 ms	516 KB	Output is correct
19	Correct	586 ms	404 KB	Output is correct
20	Correct	644 ms	400 KB	Output is correct

Subtask #5

61.0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	631 ms	644 KB	Output is correct
2	Correct	650 ms	520 KB	Output is correct
3	Correct	1065 ms	492 KB	Output is correct
4	Correct	783 ms	400 KB	Output is correct
5	Correct	739 ms	400 KB	Output is correct
6	Correct	474 ms	528 KB	Output is correct
7	Correct	626 ms	528 KB	Output is correct
8	Correct	3 ms	468 KB	Output is correct
9	Correct	6 ms	468 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Correct	519 ms	640 KB	Output is correct
12	Correct	630 ms	572 KB	Output is correct
13	Correct	1025 ms	400 KB	Output is correct
14	Correct	868 ms	400 KB	Output is correct
15	Correct	704 ms	476 KB	Output is correct
16	Correct	648 ms	656 KB	Output is correct
17	Correct	734 ms	472 KB	Output is correct
18	Correct	522 ms	748 KB	Output is correct
19	Correct	622 ms	604 KB	Output is correct
20	Correct	466 ms	508 KB	Output is correct
21	Correct	53 ms	528 KB	Output is correct
22	Correct	102 ms	684 KB	Output is correct
23	Correct	157 ms	528 KB	Output is correct
24	Correct	9 ms	468 KB	Output is correct
25	Correct	5 ms	468 KB	Output is correct
26	Correct	4 ms	468 KB	Output is correct
27	Correct	6 ms	448 KB	Output is correct
28	Correct	2 ms	468 KB	Output is correct
29	Correct	765 ms	400 KB	Output is correct
30	Correct	577 ms	512 KB	Output is correct
31	Correct	669 ms	636 KB	Output is correct
32	Correct	654 ms	400 KB	Output is correct
33	Correct	591 ms	508 KB	Output is correct
34	Correct	436 ms	528 KB	Output is correct
35	Correct	485 ms	652 KB	Output is correct
36	Correct	627 ms	600 KB	Output is correct
37	Correct	576 ms	760 KB	Output is correct
38	Correct	529 ms	632 KB	Output is correct
39	Correct	683 ms	636 KB	Output is correct
40	Correct	548 ms	640 KB	Output is correct
41	Correct	517 ms	616 KB	Output is correct
42	Correct	92 ms	532 KB	Output is correct
43	Correct	119 ms	528 KB	Output is correct
44	Correct	206 ms	528 KB	Output is correct
45	Correct	253 ms	516 KB	Output is correct
46	Correct	416 ms	528 KB	Output is correct
47	Correct	318 ms	512 KB	Output is correct
48	Correct	67 ms	656 KB	Output is correct
49	Correct	60 ms	628 KB	Output is correct