Submission #430344

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
430344	2021-06-16T13:03:06 Z	Keshi	Stations (IOI20_stations)	C++17	67.2269 / 100	1337 ms	852 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	480 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	296 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	707 ms	852 KB	Output is correct
2	Correct	648 ms	784 KB	Output is correct
3	Correct	1331 ms	520 KB	Output is correct
4	Correct	924 ms	400 KB	Output is correct
5	Correct	775 ms	564 KB	Output is correct
6	Correct	731 ms	508 KB	Output is correct
7	Correct	684 ms	528 KB	Output is correct
8	Correct	3 ms	468 KB	Output is correct
9	Correct	8 ms	596 KB	Output is correct
10	Correct	2 ms	596 KB	Output is correct
11	Correct	883 ms	512 KB	Output is correct
12	Correct	532 ms	764 KB	Output is correct
13	Correct	556 ms	624 KB	Output is correct
14	Correct	607 ms	528 KB	Output is correct
15	Correct	61 ms	548 KB	Output is correct
16	Correct	68 ms	572 KB	Output is correct
17	Correct	159 ms	656 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1337 ms	400 KB	Output is correct
2	Correct	769 ms	528 KB	Output is correct
3	Correct	761 ms	528 KB	Output is correct
4	Correct	3 ms	604 KB	Output is correct
5	Correct	6 ms	468 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	957 ms	400 KB	Output is correct
8	Correct	1123 ms	500 KB	Output is correct
9	Correct	768 ms	572 KB	Output is correct
10	Correct	654 ms	528 KB	Output is correct
11	Correct	8 ms	596 KB	Output is correct
12	Correct	8 ms	604 KB	Output is correct
13	Correct	6 ms	608 KB	Output is correct
14	Correct	5 ms	596 KB	Output is correct
15	Correct	2 ms	464 KB	Output is correct
16	Correct	595 ms	528 KB	Output is correct
17	Correct	495 ms	512 KB	Output is correct
18	Correct	622 ms	508 KB	Output is correct
19	Correct	700 ms	512 KB	Output is correct
20	Correct	847 ms	528 KB	Output is correct

Subtask #5

41.2269 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	618 ms	528 KB	Partially correct
2	Partially correct	577 ms	536 KB	Partially correct
3	Correct	1033 ms	400 KB	Output is correct
4	Correct	898 ms	508 KB	Output is correct
5	Correct	754 ms	516 KB	Output is correct
6	Partially correct	472 ms	528 KB	Partially correct
7	Partially correct	592 ms	528 KB	Partially correct
8	Correct	3 ms	848 KB	Output is correct
9	Correct	4 ms	596 KB	Output is correct
10	Correct	2 ms	596 KB	Output is correct
11	Partially correct	552 ms	504 KB	Partially correct
12	Partially correct	655 ms	508 KB	Partially correct
13	Correct	975 ms	500 KB	Output is correct
14	Correct	820 ms	400 KB	Output is correct
15	Correct	623 ms	512 KB	Output is correct
16	Partially correct	554 ms	528 KB	Partially correct
17	Correct	606 ms	524 KB	Output is correct
18	Partially correct	464 ms	756 KB	Partially correct
19	Partially correct	670 ms	764 KB	Partially correct
20	Partially correct	508 ms	656 KB	Partially correct
21	Partially correct	86 ms	528 KB	Partially correct
22	Partially correct	79 ms	548 KB	Partially correct
23	Partially correct	101 ms	736 KB	Partially correct
24	Correct	7 ms	596 KB	Output is correct
25	Correct	4 ms	596 KB	Output is correct
26	Correct	5 ms	596 KB	Output is correct
27	Correct	5 ms	604 KB	Output is correct
28	Correct	2 ms	468 KB	Output is correct
29	Correct	604 ms	508 KB	Output is correct
30	Correct	681 ms	520 KB	Output is correct
31	Correct	739 ms	512 KB	Output is correct
32	Correct	688 ms	512 KB	Output is correct
33	Correct	742 ms	508 KB	Output is correct
34	Partially correct	344 ms	628 KB	Partially correct
35	Partially correct	626 ms	780 KB	Partially correct
36	Partially correct	542 ms	528 KB	Partially correct
37	Partially correct	672 ms	732 KB	Partially correct
38	Partially correct	511 ms	596 KB	Partially correct
39	Partially correct	477 ms	628 KB	Partially correct
40	Partially correct	496 ms	632 KB	Partially correct
41	Partially correct	587 ms	612 KB	Partially correct
42	Partially correct	68 ms	660 KB	Partially correct
43	Partially correct	109 ms	532 KB	Partially correct
44	Partially correct	181 ms	612 KB	Partially correct
45	Partially correct	210 ms	508 KB	Partially correct
46	Partially correct	496 ms	512 KB	Partially correct
47	Partially correct	334 ms	616 KB	Partially correct
48	Partially correct	91 ms	744 KB	Partially correct
49	Partially correct	97 ms	760 KB	Partially correct