Submission #416590

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
416590	2021-06-02T16:32:20 Z	Dilshod_Imomov	Stations (IOI20_stations)	C++17	52.3205 / 100	1097 ms	55608 KB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1e3 + 7;
 
void dfs( vector < int > &used, vector<vector<int>> adj, int v, int p, vector<int> &lb, int &cnt ) {
	if ( used[cnt] ) {
		cnt++;
	}
	lb[v] = cnt;
	used[cnt] = 1;
	for ( auto u: adj[v] ) {
		if ( u != p ) {
			dfs( used, adj, u, v, lb, cnt );
		}
	}
	lb[v] *= 1000;
	lb[v] += cnt;
}
 
 
vector<int> label(int n, int k, vector<int> U, vector<int> V) {
	vector < vector < int > > adj(n + 1);
	for ( int i = 0; i < n - 1; i++ ) {
		int u = U[i], v = V[i];
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	vector < int > lb(n), used(n + 7);
	int cnt = 0;
	dfs( used, adj, 0, -1, lb, cnt );
	return lb;
}
 
int find_next_station(int s, int t, vector<int> c) {
	int tins = s / 1000, touts = s % 1000;
	int tint = t / 1000, toutt = t % 1000;
	int pr = -1;
	for ( auto u: c ) {
		int tinu = u / 1000, toutu = u % 1000;
		if ( tinu <= tins && toutu >= touts ) {
			pr = u;
			continue;
		}
		if ( tinu <= tint && toutu >= toutt ) {
			return u;
		}
	}
	assert( pr != -1 );
	return pr;
}

Subtask #1

0 / 5.0

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

Subtask #2

0 / 8.0

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

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	841 ms	55404 KB	Output is correct
2	Correct	1016 ms	53084 KB	Output is correct
3	Correct	922 ms	400 KB	Output is correct
4	Correct	618 ms	400 KB	Output is correct
5	Correct	585 ms	488 KB	Output is correct
6	Correct	1043 ms	53480 KB	Output is correct
7	Correct	511 ms	42764 KB	Output is correct
8	Correct	3 ms	468 KB	Output is correct
9	Correct	5 ms	468 KB	Output is correct
10	Correct	1 ms	464 KB	Output is correct
11	Correct	570 ms	488 KB	Output is correct
12	Correct	999 ms	54492 KB	Output is correct
13	Correct	1081 ms	50256 KB	Output is correct
14	Correct	493 ms	3040 KB	Output is correct
15	Correct	54 ms	420 KB	Output is correct
16	Correct	225 ms	656 KB	Output is correct
17	Correct	596 ms	676 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	815 ms	484 KB	Output is correct
2	Correct	636 ms	400 KB	Output is correct
3	Correct	566 ms	520 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	4 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	567 ms	400 KB	Output is correct
8	Correct	786 ms	404 KB	Output is correct
9	Correct	614 ms	488 KB	Output is correct
10	Correct	558 ms	400 KB	Output is correct
11	Correct	5 ms	468 KB	Output is correct
12	Correct	5 ms	480 KB	Output is correct
13	Correct	6 ms	480 KB	Output is correct
14	Correct	4 ms	468 KB	Output is correct
15	Correct	2 ms	472 KB	Output is correct
16	Correct	464 ms	528 KB	Output is correct
17	Correct	480 ms	612 KB	Output is correct
18	Correct	496 ms	400 KB	Output is correct
19	Correct	509 ms	528 KB	Output is correct
20	Correct	484 ms	492 KB	Output is correct

Subtask #5

26.3205 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	821 ms	55520 KB	Partially correct
2	Partially correct	998 ms	48864 KB	Partially correct
3	Partially correct	850 ms	528 KB	Partially correct
4	Partially correct	625 ms	488 KB	Partially correct
5	Partially correct	592 ms	400 KB	Partially correct
6	Partially correct	1033 ms	55444 KB	Partially correct
7	Partially correct	516 ms	31228 KB	Partially correct
8	Partially correct	3 ms	468 KB	Partially correct
9	Partially correct	4 ms	468 KB	Partially correct
10	Partially correct	1 ms	472 KB	Partially correct
11	Partially correct	984 ms	1096 KB	Partially correct
12	Partially correct	556 ms	1004 KB	Partially correct
13	Partially correct	826 ms	528 KB	Partially correct
14	Partially correct	637 ms	400 KB	Partially correct
15	Partially correct	557 ms	488 KB	Partially correct
16	Partially correct	488 ms	1000 KB	Partially correct
17	Partially correct	576 ms	400 KB	Partially correct
18	Partially correct	983 ms	37444 KB	Partially correct
19	Partially correct	1014 ms	51776 KB	Partially correct
20	Partially correct	497 ms	4104 KB	Partially correct
21	Partially correct	63 ms	472 KB	Partially correct
22	Partially correct	213 ms	604 KB	Partially correct
23	Partially correct	598 ms	736 KB	Partially correct
24	Partially correct	6 ms	468 KB	Partially correct
25	Partially correct	6 ms	472 KB	Partially correct
26	Partially correct	5 ms	468 KB	Partially correct
27	Partially correct	4 ms	468 KB	Partially correct
28	Partially correct	2 ms	468 KB	Partially correct
29	Partially correct	487 ms	400 KB	Partially correct
30	Partially correct	489 ms	400 KB	Partially correct
31	Partially correct	486 ms	400 KB	Partially correct
32	Partially correct	462 ms	608 KB	Partially correct
33	Partially correct	490 ms	400 KB	Partially correct
34	Partially correct	854 ms	42000 KB	Partially correct
35	Partially correct	1030 ms	55608 KB	Partially correct
36	Partially correct	1097 ms	45956 KB	Partially correct
37	Partially correct	1052 ms	13536 KB	Partially correct
38	Partially correct	1087 ms	13436 KB	Partially correct
39	Partially correct	1051 ms	17812 KB	Partially correct
40	Partially correct	1055 ms	17920 KB	Partially correct
41	Partially correct	1035 ms	14540 KB	Partially correct
42	Partially correct	343 ms	672 KB	Partially correct
43	Partially correct	583 ms	764 KB	Partially correct
44	Partially correct	576 ms	1164 KB	Partially correct
45	Partially correct	696 ms	1676 KB	Partially correct
46	Partially correct	617 ms	13956 KB	Partially correct
47	Partially correct	885 ms	26776 KB	Partially correct
48	Partially correct	530 ms	1124 KB	Partially correct
49	Partially correct	627 ms	1052 KB	Partially correct