Submission #377834

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
377834	2021-03-15T08:29:29 Z	autumn_eel	Stations (IOI20_stations)	C++14	36.3167 / 100	1063 ms	1196 KB

stations

#include "stations.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;

static vector<vector<int>>E;
static vector<int>labels;
static int cnt=0;

void dfs(int v,int p){
	int L=cnt++;
	for(int u:E[v]){
		if(u==p)continue;
		dfs(u,v);
	}
	int R=cnt;
	labels[v]=L*1001+R;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v){
	E=vector<vector<int>>(n);
	labels=vector<int>(n);
	cnt=0;
	rep(i,n-1){
		E[u[i]].push_back(v[i]);
		E[v[i]].push_back(u[i]);
	}
	dfs(0,-1);
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	int sl=s/1001,sr=s%1001;
	int tl=t/1001,tr=t%1001;
	for(int u:c){
		int ul=u/1001,ur=u%1001;
		if(ul<=sl&&sr<=ur)continue;
		if(ul<=tl&&tr<=ur)return u;
	}
	for(int u:c){
		int ul=u/1001,ur=u%1001;
		if(ul<=sl&&sr<=ur)return u;
	}
	
	return -1;
}

Subtask #1

0 / 5.0

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

Subtask #2

0 / 8.0

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

Subtask #3

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	548 KB	Invalid labels (values out of range). scenario=4, k=1000000, vertex=585, label=1000999
2	Halted	0 ms	0 KB	-

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	935 ms	756 KB	Output is correct
2	Correct	676 ms	868 KB	Output is correct
3	Correct	626 ms	756 KB	Output is correct
4	Correct	3 ms	876 KB	Output is correct
5	Correct	4 ms	916 KB	Output is correct
6	Correct	2 ms	876 KB	Output is correct
7	Correct	723 ms	736 KB	Output is correct
8	Correct	1063 ms	756 KB	Output is correct
9	Correct	727 ms	868 KB	Output is correct
10	Correct	702 ms	756 KB	Output is correct
11	Correct	7 ms	736 KB	Output is correct
12	Correct	5 ms	756 KB	Output is correct
13	Correct	7 ms	736 KB	Output is correct
14	Correct	5 ms	876 KB	Output is correct
15	Correct	2 ms	736 KB	Output is correct
16	Correct	691 ms	736 KB	Output is correct
17	Correct	696 ms	868 KB	Output is correct
18	Correct	750 ms	884 KB	Output is correct
19	Correct	612 ms	868 KB	Output is correct
20	Correct	563 ms	736 KB	Output is correct

Subtask #5

26.3167 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	670 ms	864 KB	Partially correct
2	Partially correct	634 ms	944 KB	Partially correct
3	Partially correct	1006 ms	756 KB	Partially correct
4	Partially correct	914 ms	868 KB	Partially correct
5	Partially correct	765 ms	756 KB	Partially correct
6	Partially correct	559 ms	864 KB	Partially correct
7	Partially correct	617 ms	736 KB	Partially correct
8	Partially correct	3 ms	876 KB	Partially correct
9	Partially correct	5 ms	756 KB	Partially correct
10	Partially correct	1 ms	736 KB	Partially correct
11	Partially correct	541 ms	1000 KB	Partially correct
12	Partially correct	569 ms	756 KB	Partially correct
13	Partially correct	971 ms	736 KB	Partially correct
14	Partially correct	663 ms	756 KB	Partially correct
15	Partially correct	649 ms	1060 KB	Partially correct
16	Partially correct	425 ms	896 KB	Partially correct
17	Partially correct	600 ms	736 KB	Partially correct
18	Partially correct	551 ms	1068 KB	Partially correct
19	Partially correct	547 ms	992 KB	Partially correct
20	Partially correct	543 ms	736 KB	Partially correct
21	Partially correct	72 ms	856 KB	Partially correct
22	Partially correct	101 ms	1056 KB	Partially correct
23	Partially correct	114 ms	888 KB	Partially correct
24	Partially correct	6 ms	736 KB	Partially correct
25	Partially correct	6 ms	916 KB	Partially correct
26	Partially correct	6 ms	756 KB	Partially correct
27	Partially correct	5 ms	756 KB	Partially correct
28	Partially correct	2 ms	736 KB	Partially correct
29	Partially correct	573 ms	756 KB	Partially correct
30	Partially correct	531 ms	868 KB	Partially correct
31	Partially correct	499 ms	736 KB	Partially correct
32	Partially correct	601 ms	884 KB	Partially correct
33	Partially correct	630 ms	756 KB	Partially correct
34	Partially correct	398 ms	884 KB	Partially correct
35	Partially correct	450 ms	1040 KB	Partially correct
36	Partially correct	530 ms	916 KB	Partially correct
37	Partially correct	532 ms	972 KB	Partially correct
38	Partially correct	521 ms	1004 KB	Partially correct
39	Partially correct	493 ms	1012 KB	Partially correct
40	Partially correct	508 ms	1196 KB	Partially correct
41	Partially correct	571 ms	996 KB	Partially correct
42	Partially correct	74 ms	756 KB	Partially correct
43	Partially correct	120 ms	756 KB	Partially correct
44	Partially correct	156 ms	1008 KB	Partially correct
45	Partially correct	210 ms	880 KB	Partially correct
46	Partially correct	368 ms	788 KB	Partially correct
47	Partially correct	319 ms	1008 KB	Partially correct
48	Partially correct	62 ms	884 KB	Partially correct
49	Partially correct	61 ms	992 KB	Partially correct