Submission #427317

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
427317	2021-06-14T14:15:46 Z	AugustinasJucas	Stations (IOI20_stations)	C++14	52.3205 / 100	1259 ms	816 KB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int dydis = 1000;
vector<int> gr[dydis];
int enter[dydis];
int leave[dydis];
vector<int> ret (dydis);
int dbInd = 0;
void dfs(int v, int came){
	enter[v] = dbInd++;
	for(auto x : gr[v]){
		if(x == came) continue;
		dfs(x, v);
	}
	leave[v] = dbInd;
	ret[v] = enter[v] * dydis + leave[v] - 1;
	//cout << "enter " << v << " - " << enter[v] << ", o leave " << leave[v]-1 << endl;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	for(int i = 0; i < n; i++){
		gr[i].clear();
		gr[i].clear();
	}
	dbInd = 0;
	ret.resize(n);
	for(int i = 0; i < n-1; i++){
		gr[u[i]].push_back(v[i]);
		gr[v[i]].push_back(u[i]);
	}
	dfs(0, -1);

	
	return ret;
}

int find_next_station(int s, int t, vector<int> c) {
	int enterS = s / 1000;
	int leaveS = s % 1000;
	int enterT = t / 1000;
	int leaveT = t % 1000;
//	cout << "kitas einant is " << s << " i " << t << " yra:\n";
	if(enterS <= enterT && leaveT <= leaveS){
	//	cout << enterS << " yra " << enterT << " tevas\n";
		for(auto x : c){
			int e = x / 1000;
			int l = x % 1000;
			if(e <= enterT && leaveT <= l && !(e <= enterS && leaveS <= l)){
		//		cout << "ret " << x << endl << endl;
				return x;
			}
		}
	}else{ // eisiu aukstyn
		for(auto x : c){
			int e = x / 1000;
			int l = x % 1000;
			if(e <= enterS && leaveS <= l){
			//	cout << "ret " << x << endl << endl;
				return x;
			}
		}
	}
	return c[0];
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	420 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	5 ms	448 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	720 ms	652 KB	Output is correct
2	Correct	593 ms	512 KB	Output is correct
3	Correct	1053 ms	712 KB	Output is correct
4	Correct	832 ms	528 KB	Output is correct
5	Correct	785 ms	400 KB	Output is correct
6	Correct	504 ms	544 KB	Output is correct
7	Correct	549 ms	520 KB	Output is correct
8	Correct	3 ms	596 KB	Output is correct
9	Correct	5 ms	468 KB	Output is correct
10	Correct	2 ms	596 KB	Output is correct
11	Correct	576 ms	400 KB	Output is correct
12	Correct	563 ms	528 KB	Output is correct
13	Correct	625 ms	656 KB	Output is correct
14	Correct	633 ms	520 KB	Output is correct
15	Correct	92 ms	528 KB	Output is correct
16	Correct	93 ms	656 KB	Output is correct
17	Correct	110 ms	656 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1152 ms	532 KB	Output is correct
2	Correct	869 ms	524 KB	Output is correct
3	Correct	777 ms	516 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	6 ms	464 KB	Output is correct
6	Correct	2 ms	608 KB	Output is correct
7	Correct	859 ms	400 KB	Output is correct
8	Correct	1259 ms	400 KB	Output is correct
9	Correct	814 ms	500 KB	Output is correct
10	Correct	702 ms	528 KB	Output is correct
11	Correct	5 ms	768 KB	Output is correct
12	Correct	7 ms	468 KB	Output is correct
13	Correct	4 ms	576 KB	Output is correct
14	Correct	5 ms	604 KB	Output is correct
15	Correct	2 ms	724 KB	Output is correct
16	Correct	613 ms	552 KB	Output is correct
17	Correct	591 ms	524 KB	Output is correct
18	Correct	686 ms	644 KB	Output is correct
19	Correct	661 ms	472 KB	Output is correct
20	Correct	622 ms	816 KB	Output is correct

Subtask #5

26.3205 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	716 ms	528 KB	Partially correct
2	Partially correct	598 ms	656 KB	Partially correct
3	Partially correct	1101 ms	400 KB	Partially correct
4	Partially correct	720 ms	516 KB	Partially correct
5	Partially correct	807 ms	528 KB	Partially correct
6	Partially correct	572 ms	512 KB	Partially correct
7	Partially correct	635 ms	528 KB	Partially correct
8	Partially correct	3 ms	588 KB	Partially correct
9	Partially correct	4 ms	604 KB	Partially correct
10	Partially correct	2 ms	604 KB	Partially correct
11	Partially correct	501 ms	496 KB	Partially correct
12	Partially correct	635 ms	516 KB	Partially correct
13	Partially correct	1055 ms	400 KB	Partially correct
14	Partially correct	938 ms	552 KB	Partially correct
15	Partially correct	733 ms	516 KB	Partially correct
16	Partially correct	543 ms	508 KB	Partially correct
17	Partially correct	807 ms	528 KB	Partially correct
18	Partially correct	512 ms	628 KB	Partially correct
19	Partially correct	494 ms	640 KB	Partially correct
20	Partially correct	642 ms	508 KB	Partially correct
21	Partially correct	51 ms	528 KB	Partially correct
22	Partially correct	86 ms	656 KB	Partially correct
23	Partially correct	154 ms	656 KB	Partially correct
24	Partially correct	5 ms	704 KB	Partially correct
25	Partially correct	9 ms	592 KB	Partially correct
26	Partially correct	4 ms	604 KB	Partially correct
27	Partially correct	5 ms	432 KB	Partially correct
28	Partially correct	3 ms	724 KB	Partially correct
29	Partially correct	845 ms	400 KB	Partially correct
30	Partially correct	766 ms	524 KB	Partially correct
31	Partially correct	690 ms	528 KB	Partially correct
32	Partially correct	486 ms	516 KB	Partially correct
33	Partially correct	475 ms	516 KB	Partially correct
34	Partially correct	366 ms	512 KB	Partially correct
35	Partially correct	696 ms	620 KB	Partially correct
36	Partially correct	569 ms	644 KB	Partially correct
37	Partially correct	599 ms	612 KB	Partially correct
38	Partially correct	557 ms	628 KB	Partially correct
39	Partially correct	492 ms	632 KB	Partially correct
40	Partially correct	638 ms	624 KB	Partially correct
41	Partially correct	549 ms	752 KB	Partially correct
42	Partially correct	75 ms	644 KB	Partially correct
43	Partially correct	106 ms	724 KB	Partially correct
44	Partially correct	163 ms	604 KB	Partially correct
45	Partially correct	258 ms	528 KB	Partially correct
46	Partially correct	442 ms	656 KB	Partially correct
47	Partially correct	489 ms	528 KB	Partially correct
48	Partially correct	73 ms	644 KB	Partially correct
49	Partially correct	56 ms	752 KB	Partially correct