Submission #311935

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
311935	2020-10-12T03:28:37 Z	denverjin	Stations (IOI20_stations)	C++14	100 / 100	1267 ms	1072 KB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

vector <int> label(int n, int k, vector <int> u, vector <int> v) {
	vector <vector <int> > g(n);
	rep(i, n - 1) {
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}
	vector <int> dfn(n), ed(n), dep(n);
	int tme = 0;
	function <void(int, int)> dfs;
	dfs = [&] (int u, int p) {
		dfn[u] = tme ++;
		rep(i, g[u].size()) {
			int v = g[u][i];
			if (v == p) continue;
			dep[v] = dep[u] + 1;
			dfs(v, u);
		}
		ed[u] = tme ++;
	};
	dfs(0, -1);
	vector <int> V;
	rep(i, n) V.pb(dep[i] & 1 ? ed[i] : dfn[i]);
	sort(V.begin(), V.end());
	vector <int> lbl(n);
	rep(i, n) lbl[i] = lower_bound(V.begin(), V.end(), dep[i] & 1 ? ed[i] : dfn[i]) - V.begin();
	return lbl;
}

int find_next_station(int s, int t, vector <int> c) {
	bool dfn_ed = 0;
	rep(i, c.size()) dfn_ed |= s > c[i];
	if (dfn_ed == 0) {
		sort(c.begin(), c.end());
		rep(i, c.size() - (s != 0)) {
			int dfn = (i ? c[i - 1] : s) + 1, ed = c[i];
			if (dfn <= t && t <= ed) return c[i];
		}
		return c.back();
	} else {
		sort(c.begin(), c.end());
		rep(i, c.size()) if (i) {
			int dfn = c[i], ed = (i + 1 < (int) c.size() ? c[i + 1] : s) - 1;
			if (dfn <= t && t <= ed) return c[i];
		}
		return c[0];
	}
	return -1;
}

#ifdef DEBUG
int main() {
	vector <int> lbl = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
	cerr << find_next_station(lbl[2], lbl[0], {lbl[1], lbl[4]}) << " " << lbl[1] << endl;
	cerr << find_next_station(lbl[1], lbl[3], {lbl[0], lbl[2], lbl[3]}) << " " << lbl[3] << endl;
	return 0;
}
#endif

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	483 ms	1024 KB	Output is correct
2	Correct	419 ms	1024 KB	Output is correct
3	Correct	725 ms	644 KB	Output is correct
4	Correct	723 ms	640 KB	Output is correct
5	Correct	702 ms	648 KB	Output is correct
6	Correct	560 ms	1008 KB	Output is correct
7	Correct	608 ms	1024 KB	Output is correct
8	Correct	2 ms	648 KB	Output is correct
9	Correct	5 ms	644 KB	Output is correct
10	Correct	2 ms	640 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	408 ms	760 KB	Output is correct
2	Correct	531 ms	808 KB	Output is correct
3	Correct	840 ms	640 KB	Output is correct
4	Correct	576 ms	640 KB	Output is correct
5	Correct	738 ms	640 KB	Output is correct
6	Correct	427 ms	760 KB	Output is correct

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	437 ms	1008 KB	Output is correct
2	Correct	378 ms	1008 KB	Output is correct
3	Correct	818 ms	644 KB	Output is correct
4	Correct	734 ms	640 KB	Output is correct
5	Correct	674 ms	640 KB	Output is correct
6	Correct	584 ms	1024 KB	Output is correct
7	Correct	473 ms	1024 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	5 ms	640 KB	Output is correct
10	Correct	1 ms	644 KB	Output is correct
11	Correct	802 ms	644 KB	Output is correct
12	Correct	591 ms	1024 KB	Output is correct
13	Correct	633 ms	1024 KB	Output is correct
14	Correct	563 ms	812 KB	Output is correct
15	Correct	64 ms	888 KB	Output is correct
16	Correct	85 ms	768 KB	Output is correct
17	Correct	142 ms	808 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1130 ms	648 KB	Output is correct
2	Correct	838 ms	648 KB	Output is correct
3	Correct	749 ms	640 KB	Output is correct
4	Correct	3 ms	640 KB	Output is correct
5	Correct	4 ms	648 KB	Output is correct
6	Correct	2 ms	640 KB	Output is correct
7	Correct	806 ms	744 KB	Output is correct
8	Correct	1073 ms	640 KB	Output is correct
9	Correct	596 ms	640 KB	Output is correct
10	Correct	601 ms	640 KB	Output is correct
11	Correct	5 ms	640 KB	Output is correct
12	Correct	8 ms	640 KB	Output is correct
13	Correct	5 ms	640 KB	Output is correct
14	Correct	6 ms	640 KB	Output is correct
15	Correct	2 ms	640 KB	Output is correct
16	Correct	664 ms	748 KB	Output is correct
17	Correct	523 ms	692 KB	Output is correct
18	Correct	467 ms	640 KB	Output is correct
19	Correct	705 ms	640 KB	Output is correct
20	Correct	515 ms	756 KB	Output is correct

Subtask #5
61.0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	800 ms	984 KB	Output is correct
2	Correct	477 ms	1008 KB	Output is correct
3	Correct	1267 ms	748 KB	Output is correct
4	Correct	644 ms	640 KB	Output is correct
5	Correct	596 ms	644 KB	Output is correct
6	Correct	550 ms	1024 KB	Output is correct
7	Correct	572 ms	992 KB	Output is correct
8	Correct	3 ms	640 KB	Output is correct
9	Correct	4 ms	640 KB	Output is correct
10	Correct	2 ms	644 KB	Output is correct
11	Correct	521 ms	832 KB	Output is correct
12	Correct	557 ms	760 KB	Output is correct
13	Correct	1047 ms	640 KB	Output is correct
14	Correct	899 ms	640 KB	Output is correct
15	Correct	554 ms	756 KB	Output is correct
16	Correct	452 ms	768 KB	Output is correct
17	Correct	583 ms	640 KB	Output is correct
18	Correct	431 ms	1024 KB	Output is correct
19	Correct	421 ms	1072 KB	Output is correct
20	Correct	502 ms	768 KB	Output is correct
21	Correct	65 ms	768 KB	Output is correct
22	Correct	86 ms	768 KB	Output is correct
23	Correct	128 ms	768 KB	Output is correct
24	Correct	5 ms	640 KB	Output is correct
25	Correct	6 ms	640 KB	Output is correct
26	Correct	4 ms	768 KB	Output is correct
27	Correct	4 ms	640 KB	Output is correct
28	Correct	2 ms	640 KB	Output is correct
29	Correct	616 ms	640 KB	Output is correct
30	Correct	740 ms	640 KB	Output is correct
31	Correct	691 ms	644 KB	Output is correct
32	Correct	538 ms	640 KB	Output is correct
33	Correct	692 ms	644 KB	Output is correct
34	Correct	334 ms	1008 KB	Output is correct
35	Correct	454 ms	1024 KB	Output is correct
36	Correct	509 ms	1024 KB	Output is correct
37	Correct	629 ms	760 KB	Output is correct
38	Correct	591 ms	848 KB	Output is correct
39	Correct	623 ms	904 KB	Output is correct
40	Correct	628 ms	768 KB	Output is correct
41	Correct	560 ms	796 KB	Output is correct
42	Correct	59 ms	768 KB	Output is correct
43	Correct	97 ms	768 KB	Output is correct
44	Correct	132 ms	768 KB	Output is correct
45	Correct	194 ms	804 KB	Output is correct
46	Correct	415 ms	812 KB	Output is correct
47	Correct	371 ms	1008 KB	Output is correct
48	Correct	93 ms	960 KB	Output is correct
49	Correct	81 ms	812 KB	Output is correct

Submission #311935

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