Submission #430365

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
430365	2021-06-16T13:10:14 Z	Keshi	Stations (IOI20_stations)	C++17	67.2269 / 100	1480 ms	940 KB

stations

//In the name of God
#include<bits/stdc++.h>
#include "stations.h"
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 1100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define Mp make_pair
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define Sz(x) ll((x).size())

ll t, st[maxn], ft[maxn], h[maxn];
vector<ll> g[maxn];

void dfs(ll v, ll p){
	st[v] = t++;
	for(ll u : g[v]){
		if(u != p){
			h[u] = h[v] + 1;
			dfs(u, v);
		}
	}
	ft[v] = t++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	for(ll i = 0; i < n; i++){
		g[i].clear();
	}
	vector<int> labels(n);
	for(ll i = 0; i < n - 1; i++){
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}
	dfs(0, 0);
	for (int i = 0; i < n; i++) {
		if(h[i] & 1) labels[i] = ft[i];
		else labels[i] = st[i];
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c){
	if(Sz(c) == 1) return c[0];
	sort(all(c));
	if(s < c[0]){
		ll ls = s + 1;
		for(ll i = 0; i < Sz(c) - 1; i++){
			if(ls <= t && t <= c[i]) return c[i];
			ls = c[i] + 1;
		}
		return c.back();
	}
	ll ls = s - 1;
	for(ll i = Sz(c) - 1; i > 0; i--){
		if(c[i] <= t && t <= ls) return c[i];
		ls = c[i] - 1;
	}
	return c[0];
}

Subtask #1

0 / 5.0

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

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	308 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	816 ms	640 KB	Output is correct
2	Correct	701 ms	636 KB	Output is correct
3	Correct	989 ms	720 KB	Output is correct
4	Correct	903 ms	504 KB	Output is correct
5	Correct	991 ms	528 KB	Output is correct
6	Correct	770 ms	632 KB	Output is correct
7	Correct	518 ms	528 KB	Output is correct
8	Correct	4 ms	596 KB	Output is correct
9	Correct	4 ms	548 KB	Output is correct
10	Correct	2 ms	528 KB	Output is correct
11	Correct	631 ms	500 KB	Output is correct
12	Correct	565 ms	740 KB	Output is correct
13	Correct	655 ms	668 KB	Output is correct
14	Correct	655 ms	528 KB	Output is correct
15	Correct	81 ms	540 KB	Output is correct
16	Correct	99 ms	528 KB	Output is correct
17	Correct	131 ms	676 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1126 ms	508 KB	Output is correct
2	Correct	787 ms	456 KB	Output is correct
3	Correct	779 ms	528 KB	Output is correct
4	Correct	3 ms	464 KB	Output is correct
5	Correct	7 ms	628 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	689 ms	492 KB	Output is correct
8	Correct	1037 ms	512 KB	Output is correct
9	Correct	784 ms	520 KB	Output is correct
10	Correct	840 ms	528 KB	Output is correct
11	Correct	4 ms	528 KB	Output is correct
12	Correct	6 ms	596 KB	Output is correct
13	Correct	5 ms	596 KB	Output is correct
14	Correct	4 ms	616 KB	Output is correct
15	Correct	2 ms	548 KB	Output is correct
16	Correct	646 ms	512 KB	Output is correct
17	Correct	707 ms	508 KB	Output is correct
18	Correct	728 ms	516 KB	Output is correct
19	Correct	719 ms	528 KB	Output is correct
20	Correct	583 ms	528 KB	Output is correct

Subtask #5

41.2269 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	682 ms	616 KB	Partially correct
2	Partially correct	475 ms	652 KB	Partially correct
3	Correct	1480 ms	508 KB	Output is correct
4	Correct	745 ms	400 KB	Output is correct
5	Correct	757 ms	508 KB	Output is correct
6	Partially correct	697 ms	520 KB	Partially correct
7	Partially correct	506 ms	528 KB	Partially correct
8	Correct	5 ms	596 KB	Output is correct
9	Correct	11 ms	484 KB	Output is correct
10	Correct	2 ms	400 KB	Output is correct
11	Partially correct	466 ms	528 KB	Partially correct
12	Partially correct	629 ms	508 KB	Partially correct
13	Correct	1307 ms	528 KB	Output is correct
14	Correct	963 ms	572 KB	Output is correct
15	Correct	799 ms	512 KB	Output is correct
16	Partially correct	616 ms	520 KB	Partially correct
17	Correct	727 ms	584 KB	Output is correct
18	Partially correct	580 ms	636 KB	Partially correct
19	Partially correct	634 ms	648 KB	Partially correct
20	Partially correct	615 ms	616 KB	Partially correct
21	Partially correct	62 ms	596 KB	Partially correct
22	Partially correct	71 ms	528 KB	Partially correct
23	Partially correct	168 ms	516 KB	Partially correct
24	Correct	7 ms	596 KB	Output is correct
25	Correct	7 ms	420 KB	Output is correct
26	Correct	3 ms	596 KB	Output is correct
27	Correct	5 ms	712 KB	Output is correct
28	Correct	3 ms	596 KB	Output is correct
29	Correct	642 ms	604 KB	Output is correct
30	Correct	694 ms	488 KB	Output is correct
31	Correct	622 ms	584 KB	Output is correct
32	Correct	783 ms	660 KB	Output is correct
33	Correct	642 ms	532 KB	Output is correct
34	Partially correct	453 ms	500 KB	Partially correct
35	Partially correct	456 ms	748 KB	Partially correct
36	Partially correct	564 ms	768 KB	Partially correct
37	Partially correct	489 ms	824 KB	Partially correct
38	Partially correct	508 ms	748 KB	Partially correct
39	Partially correct	582 ms	728 KB	Partially correct
40	Partially correct	632 ms	616 KB	Partially correct
41	Partially correct	606 ms	672 KB	Partially correct
42	Partially correct	87 ms	804 KB	Partially correct
43	Partially correct	152 ms	852 KB	Partially correct
44	Partially correct	137 ms	516 KB	Partially correct
45	Partially correct	180 ms	508 KB	Partially correct
46	Partially correct	375 ms	528 KB	Partially correct
47	Partially correct	483 ms	528 KB	Partially correct
48	Partially correct	92 ms	940 KB	Partially correct
49	Partially correct	63 ms	776 KB	Partially correct