Submission #308587

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
308587	2020-10-01T14:52:06 Z	lacito	Stations (IOI20_stations)	C++14	52.3206 / 100	1136 ms	1024 KB

stations

#include "stations.h"
#include <vector>

using namespace std;

const int M = 1000;

vector<vector<int>> g;
vector<int> intime, outtime;
int itime, otime;

void dfs(int v) {
    intime[v] = itime++;
    for (int x : g[v])
        if (intime[x] == -1)
            dfs(x);
    outtime[v] = otime++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	g.assign(n, {});
	intime.assign(n, -1);
	outtime.assign(n, -1);
	for (int i = 0; i < n - 1; i++) {
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
	}
	itime = 0;
	otime = 0;
	dfs(0);
	vector<int> labels(n);
	for (int i = 0; i < n; i++) {
		labels[i] = M * intime[i] + outtime[i];
	}
	return labels;
}

inline int in(int label) {
    return label / M;
}

inline int out(int label) {
    return label % M;
}

inline bool inside(int label_a, int label_b) {
    return in(label_a) <= in(label_b) && out(label_b) <= out(label_a);
}

int find_next_station(int s, int t, vector<int> c) {
    int parent = -1;
    for (int x : c) {
        if (inside(x, s))
            parent = x;
    }
    for (int x : c) {
        if (inside(x, t) && x != parent)
            return x;
    }
	return parent;
}

Subtask #1

0 / 5.0

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

Subtask #2

0 / 8.0

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

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	565 ms	1008 KB	Output is correct
2	Correct	498 ms	768 KB	Output is correct
3	Correct	1136 ms	836 KB	Output is correct
4	Correct	792 ms	640 KB	Output is correct
5	Correct	940 ms	752 KB	Output is correct
6	Correct	526 ms	764 KB	Output is correct
7	Correct	518 ms	760 KB	Output is correct
8	Correct	3 ms	664 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	1 ms	660 KB	Output is correct
11	Correct	612 ms	732 KB	Output is correct
12	Correct	639 ms	800 KB	Output is correct
13	Correct	588 ms	880 KB	Output is correct
14	Correct	496 ms	828 KB	Output is correct
15	Correct	57 ms	640 KB	Output is correct
16	Correct	82 ms	856 KB	Output is correct
17	Correct	117 ms	812 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1053 ms	640 KB	Output is correct
2	Correct	761 ms	744 KB	Output is correct
3	Correct	656 ms	640 KB	Output is correct
4	Correct	2 ms	664 KB	Output is correct
5	Correct	5 ms	640 KB	Output is correct
6	Correct	0 ms	664 KB	Output is correct
7	Correct	812 ms	640 KB	Output is correct
8	Correct	991 ms	640 KB	Output is correct
9	Correct	846 ms	768 KB	Output is correct
10	Correct	645 ms	660 KB	Output is correct
11	Correct	6 ms	920 KB	Output is correct
12	Correct	5 ms	640 KB	Output is correct
13	Correct	3 ms	640 KB	Output is correct
14	Correct	4 ms	664 KB	Output is correct
15	Correct	1 ms	640 KB	Output is correct
16	Correct	640 ms	744 KB	Output is correct
17	Correct	608 ms	744 KB	Output is correct
18	Correct	539 ms	656 KB	Output is correct
19	Correct	545 ms	640 KB	Output is correct
20	Correct	583 ms	768 KB	Output is correct

Subtask #5

26.3206 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	678 ms	1024 KB	Partially correct
2	Partially correct	497 ms	768 KB	Partially correct
3	Correct	1043 ms	740 KB	Output is correct
4	Partially correct	948 ms	640 KB	Partially correct
5	Partially correct	978 ms	776 KB	Partially correct
6	Partially correct	644 ms	768 KB	Partially correct
7	Partially correct	576 ms	740 KB	Partially correct
8	Partially correct	3 ms	800 KB	Partially correct
9	Partially correct	8 ms	640 KB	Partially correct
10	Partially correct	0 ms	668 KB	Partially correct
11	Partially correct	476 ms	768 KB	Partially correct
12	Partially correct	603 ms	828 KB	Partially correct
13	Correct	916 ms	656 KB	Output is correct
14	Partially correct	620 ms	656 KB	Partially correct
15	Partially correct	747 ms	660 KB	Partially correct
16	Partially correct	578 ms	740 KB	Partially correct
17	Partially correct	654 ms	640 KB	Partially correct
18	Partially correct	552 ms	1016 KB	Partially correct
19	Partially correct	489 ms	888 KB	Partially correct
20	Partially correct	590 ms	968 KB	Partially correct
21	Partially correct	75 ms	652 KB	Partially correct
22	Partially correct	81 ms	856 KB	Partially correct
23	Partially correct	112 ms	780 KB	Partially correct
24	Partially correct	7 ms	668 KB	Partially correct
25	Partially correct	6 ms	640 KB	Partially correct
26	Partially correct	4 ms	640 KB	Partially correct
27	Partially correct	3 ms	640 KB	Partially correct
28	Partially correct	1 ms	640 KB	Partially correct
29	Partially correct	582 ms	640 KB	Partially correct
30	Partially correct	558 ms	664 KB	Partially correct
31	Partially correct	556 ms	660 KB	Partially correct
32	Partially correct	638 ms	660 KB	Partially correct
33	Partially correct	566 ms	660 KB	Partially correct
34	Partially correct	324 ms	1024 KB	Partially correct
35	Partially correct	624 ms	784 KB	Partially correct
36	Partially correct	469 ms	1020 KB	Partially correct
37	Partially correct	526 ms	776 KB	Partially correct
38	Partially correct	488 ms	776 KB	Partially correct
39	Partially correct	506 ms	796 KB	Partially correct
40	Partially correct	474 ms	768 KB	Partially correct
41	Partially correct	445 ms	808 KB	Partially correct
42	Partially correct	58 ms	836 KB	Partially correct
43	Partially correct	103 ms	840 KB	Partially correct
44	Partially correct	133 ms	768 KB	Partially correct
45	Partially correct	163 ms	792 KB	Partially correct
46	Partially correct	303 ms	1024 KB	Partially correct
47	Partially correct	332 ms	816 KB	Partially correct
48	Partially correct	68 ms	788 KB	Partially correct
49	Partially correct	59 ms	768 KB	Partially correct