Submission #314824

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
314824	2020-10-21T11:32:59 Z	kostia244	Stations (IOI20_stations)	C++17	76 / 100	1075 ms	1120 KB

stations

#include "stations.h"
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
namespace lab {
vector<vector<int>> g;
vector<int> tin, tout, d;
int timer;
void dfs(int v, int p) {
	tin[v] = ++timer;
	for(auto &i : g[v]) if(i != p) {
		d[i] = d[v]+1;
		dfs(i, v);
	}
	tout[v] = ++timer;
}
};
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	using namespace lab;
	timer = -1;
	tin = tout = d = vector<int>(n);
	g.assign(n, vector<int>());
	for(int i = 0; i+1 < n; i++) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs(0, 0);
	std::vector<int> labels(n);
	for (int i = 0; i < n; i++) {
		labels[i] = (d[i]&1) ? tout[i] : tin[i];
	}
	return labels;
}
int rv(int a) { return a; }
int find_next_station(int s, int t, std::vector<int> c) {
	int type, par;
	type = s > *max_element(all(c));//tout
	if(s) {
		if(type == 0) {//tin here, tout in neighbors
			par = *max_element(all(c));
			c.erase(max_element(all(c)));
		} else {//tout here
			par = *min_element(all(c));
			c.erase(min_element(all(c)));
		}
	} else par = -1;
	if(!type) {
		if(rv(t) < rv(s)) return par;
		int mn = 1<<30;
		for(auto &i : c) if(rv(t) <= rv(i)) mn = min(mn, i);
		if(mn == 1<<30) mn = par;
		return mn;
	}
	if(t > s) return par;
	int mx = -1;
	for(auto &i : c) if(rv(t) >= rv(i)) mx = max(mx, i);
	if(mx == -1) mx = par;
	return mx;
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	512 KB	Invalid labels (values out of range). scenario=2, k=1000, vertex=1, label=1990
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	488 KB	Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1022
2	Halted	0 ms	0 KB	-

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	532 ms	984 KB	Output is correct
2	Correct	495 ms	1016 KB	Output is correct
3	Correct	879 ms	776 KB	Output is correct
4	Correct	640 ms	644 KB	Output is correct
5	Correct	604 ms	640 KB	Output is correct
6	Correct	481 ms	1024 KB	Output is correct
7	Correct	458 ms	768 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	5 ms	804 KB	Output is correct
10	Correct	2 ms	640 KB	Output is correct
11	Correct	585 ms	640 KB	Output is correct
12	Correct	455 ms	1120 KB	Output is correct
13	Correct	458 ms	1024 KB	Output is correct
14	Correct	465 ms	828 KB	Output is correct
15	Correct	57 ms	768 KB	Output is correct
16	Correct	74 ms	980 KB	Output is correct
17	Correct	113 ms	804 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	882 ms	640 KB	Output is correct
2	Correct	681 ms	784 KB	Output is correct
3	Correct	575 ms	760 KB	Output is correct
4	Correct	2 ms	640 KB	Output is correct
5	Correct	4 ms	648 KB	Output is correct
6	Correct	0 ms	640 KB	Output is correct
7	Correct	623 ms	648 KB	Output is correct
8	Correct	954 ms	640 KB	Output is correct
9	Correct	796 ms	640 KB	Output is correct
10	Correct	733 ms	644 KB	Output is correct
11	Correct	6 ms	652 KB	Output is correct
12	Correct	5 ms	640 KB	Output is correct
13	Correct	4 ms	648 KB	Output is correct
14	Correct	4 ms	892 KB	Output is correct
15	Correct	1 ms	640 KB	Output is correct
16	Correct	568 ms	640 KB	Output is correct
17	Correct	543 ms	640 KB	Output is correct
18	Correct	518 ms	640 KB	Output is correct
19	Correct	550 ms	768 KB	Output is correct
20	Correct	566 ms	652 KB	Output is correct

Subtask #5

50.0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	559 ms	1016 KB	Partially correct
2	Partially correct	450 ms	1016 KB	Partially correct
3	Correct	895 ms	640 KB	Output is correct
4	Correct	678 ms	896 KB	Output is correct
5	Correct	593 ms	644 KB	Output is correct
6	Partially correct	472 ms	1024 KB	Partially correct
7	Partially correct	458 ms	768 KB	Partially correct
8	Correct	3 ms	648 KB	Output is correct
9	Correct	5 ms	640 KB	Output is correct
10	Correct	1 ms	644 KB	Output is correct
11	Partially correct	582 ms	992 KB	Partially correct
12	Partially correct	667 ms	808 KB	Partially correct
13	Correct	1075 ms	652 KB	Output is correct
14	Correct	746 ms	640 KB	Output is correct
15	Correct	692 ms	640 KB	Output is correct
16	Partially correct	473 ms	816 KB	Partially correct
17	Correct	641 ms	900 KB	Output is correct
18	Partially correct	511 ms	1012 KB	Partially correct
19	Partially correct	513 ms	1024 KB	Partially correct
20	Partially correct	589 ms	768 KB	Partially correct
21	Correct	59 ms	640 KB	Output is correct
22	Partially correct	77 ms	768 KB	Partially correct
23	Partially correct	142 ms	768 KB	Partially correct
24	Correct	5 ms	656 KB	Output is correct
25	Correct	6 ms	640 KB	Output is correct
26	Correct	5 ms	644 KB	Output is correct
27	Correct	4 ms	656 KB	Output is correct
28	Correct	2 ms	644 KB	Output is correct
29	Correct	508 ms	768 KB	Output is correct
30	Correct	641 ms	644 KB	Output is correct
31	Correct	557 ms	640 KB	Output is correct
32	Correct	683 ms	648 KB	Output is correct
33	Correct	749 ms	640 KB	Output is correct
34	Partially correct	334 ms	1016 KB	Partially correct
35	Partially correct	551 ms	1104 KB	Partially correct
36	Partially correct	518 ms	1084 KB	Partially correct
37	Partially correct	501 ms	1016 KB	Partially correct
38	Partially correct	498 ms	1108 KB	Partially correct
39	Partially correct	544 ms	992 KB	Partially correct
40	Partially correct	452 ms	992 KB	Partially correct
41	Partially correct	525 ms	892 KB	Partially correct
42	Partially correct	67 ms	768 KB	Partially correct
43	Partially correct	139 ms	796 KB	Partially correct
44	Partially correct	122 ms	768 KB	Partially correct
45	Partially correct	168 ms	768 KB	Partially correct
46	Partially correct	344 ms	824 KB	Partially correct
47	Partially correct	334 ms	796 KB	Partially correct
48	Partially correct	71 ms	768 KB	Partially correct
49	Partially correct	74 ms	1024 KB	Partially correct