Submission #431621

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
431621	2021-06-17T13:41:22 Z	dreezy	Stations (IOI20_stations)	C++17	76 / 100	934 ms	868 KB

stations

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

#define ll long long
#define pb push_back
#define pi pair<int,int>

vector<int> labels;
vector<vector<int>> graph;

vector<pi> ord;
int cnt = 0;
void dfs1(int n,int p){//calc sizes
	ord[n].first = cnt++;
	for(int adj : graph[n])
	{
		if(adj == p) continue;
		dfs1(adj, n);
	}
	ord[n].second = cnt++;
}



void name_subtree(int n, int p, bool first){
	if(first)
		labels[n] = ord[n].first;
	else
		labels[n] = ord[n].second;
	for(int adj : graph[n]){
		if(adj == p)
		continue;
		name_subtree(adj, n, !first);
	}
}


vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	cnt = 0;
	ord.clear();
	labels.clear();
	graph.clear();
	ord.assign(n, {0,0});
	labels.assign(n, 0);
	graph.assign( n, vector<int>());
	for (int i = 0; i < n - 1; i++) {
		graph[u[i]].pb(v[i]);
		graph[v[i]].pb(u[i]);
	}
	

	dfs1(0,-1);
	int root = 0;
	//for(int i =0; i<n; i++) cout <<i<<": "<< ord[i].first<<", "<<ord[i].second<<endl;
	
	name_subtree(root, -1, 1);
	//for(int i =0; i<n; i++) cout <<i<<": "<< labels[i]<<endl;
	
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	if(c.size() == 1) return c[0];
	
	bool isfirst = c[0] > s;

	
	if(isfirst){
		if(t < s) return c[c.size() - 1];
		for(int adj : c){
			if(t <= adj) return adj;
		}
		return c[c.size()-1] ;
	}
	else{
		reverse(c.begin(), c.end());
		if( t > s) return c[c.size()-1];
		for(int adj : c)
			if(t >= adj)
				return adj;
		return c[c.size()-1];
	}
	

}


/************/

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	468 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	408 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	523 ms	604 KB	Output is correct
2	Correct	510 ms	604 KB	Output is correct
3	Correct	934 ms	484 KB	Output is correct
4	Correct	778 ms	488 KB	Output is correct
5	Correct	606 ms	472 KB	Output is correct
6	Correct	461 ms	528 KB	Output is correct
7	Correct	403 ms	528 KB	Output is correct
8	Correct	3 ms	468 KB	Output is correct
9	Correct	4 ms	468 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Correct	570 ms	504 KB	Output is correct
12	Correct	466 ms	868 KB	Output is correct
13	Correct	460 ms	676 KB	Output is correct
14	Correct	468 ms	488 KB	Output is correct
15	Correct	57 ms	468 KB	Output is correct
16	Correct	62 ms	528 KB	Output is correct
17	Correct	109 ms	560 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	889 ms	552 KB	Output is correct
2	Correct	658 ms	520 KB	Output is correct
3	Correct	626 ms	488 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	4 ms	468 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	624 ms	480 KB	Output is correct
8	Correct	911 ms	404 KB	Output is correct
9	Correct	664 ms	400 KB	Output is correct
10	Correct	605 ms	480 KB	Output is correct
11	Correct	6 ms	468 KB	Output is correct
12	Correct	7 ms	468 KB	Output is correct
13	Correct	5 ms	468 KB	Output is correct
14	Correct	3 ms	448 KB	Output is correct
15	Correct	2 ms	468 KB	Output is correct
16	Correct	526 ms	488 KB	Output is correct
17	Correct	539 ms	528 KB	Output is correct
18	Correct	542 ms	404 KB	Output is correct
19	Correct	527 ms	488 KB	Output is correct
20	Correct	515 ms	488 KB	Output is correct

Subtask #5

50.0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	565 ms	652 KB	Partially correct
2	Partially correct	467 ms	600 KB	Partially correct
3	Correct	920 ms	400 KB	Output is correct
4	Correct	724 ms	400 KB	Output is correct
5	Correct	626 ms	488 KB	Output is correct
6	Partially correct	472 ms	520 KB	Partially correct
7	Partially correct	461 ms	484 KB	Partially correct
8	Correct	5 ms	468 KB	Output is correct
9	Correct	7 ms	428 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Partially correct	447 ms	584 KB	Partially correct
12	Partially correct	489 ms	528 KB	Partially correct
13	Correct	879 ms	456 KB	Output is correct
14	Correct	652 ms	520 KB	Output is correct
15	Correct	616 ms	400 KB	Output is correct
16	Partially correct	465 ms	528 KB	Partially correct
17	Correct	599 ms	400 KB	Output is correct
18	Partially correct	487 ms	624 KB	Partially correct
19	Partially correct	426 ms	668 KB	Partially correct
20	Partially correct	451 ms	528 KB	Partially correct
21	Correct	57 ms	416 KB	Output is correct
22	Partially correct	73 ms	532 KB	Partially correct
23	Partially correct	120 ms	588 KB	Partially correct
24	Correct	7 ms	480 KB	Output is correct
25	Correct	8 ms	472 KB	Output is correct
26	Correct	6 ms	468 KB	Output is correct
27	Correct	6 ms	540 KB	Output is correct
28	Correct	5 ms	468 KB	Output is correct
29	Correct	518 ms	488 KB	Output is correct
30	Correct	632 ms	488 KB	Output is correct
31	Correct	551 ms	656 KB	Output is correct
32	Correct	539 ms	488 KB	Output is correct
33	Correct	554 ms	476 KB	Output is correct
34	Partially correct	306 ms	624 KB	Partially correct
35	Partially correct	436 ms	656 KB	Partially correct
36	Partially correct	453 ms	712 KB	Partially correct
37	Partially correct	427 ms	748 KB	Partially correct
38	Partially correct	482 ms	720 KB	Partially correct
39	Partially correct	494 ms	732 KB	Partially correct
40	Partially correct	471 ms	732 KB	Partially correct
41	Partially correct	415 ms	608 KB	Partially correct
42	Partially correct	78 ms	528 KB	Partially correct
43	Partially correct	119 ms	528 KB	Partially correct
44	Partially correct	135 ms	528 KB	Partially correct
45	Partially correct	153 ms	596 KB	Partially correct
46	Partially correct	296 ms	484 KB	Partially correct
47	Partially correct	312 ms	528 KB	Partially correct
48	Partially correct	74 ms	572 KB	Partially correct
49	Partially correct	57 ms	780 KB	Partially correct