Submission #824753

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
824753	2023-08-14T09:34:22 Z	fatemetmhr	Stations (IOI20_stations)	C++17	100 / 100	668 ms	5544 KB

stations

// Be name khoda //



#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << "(" << #x << "):" << x << endl;
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define pb       push_back
#define mp       make_pair

const int maxn5 = 1e5 + 10;

vector <int> ret, adj[maxn5];
int h[maxn5], st[maxn5], ft[maxn5], ti;
bool mark[maxn5];

void dfs(int v){
	mark[v] = true;
	st[v] = ++ti;
	for(auto u : adj[v]) if(!mark[u]){
		h[u] = h[v] + 1;
		dfs(u);
	}
	ft[v] = ++ti;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	ret.clear();
	ret.resize(n);
	h[0] = 0;
	ti = -1;
	fill(mark, mark + n + 4, false);
	for(int i = 0; i < n; i++){
		adj[i].clear();
	}
	for(int i = 0; i < n - 1; i++){
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
	dfs(0);
	for(int i = 0; i < n; i++){
		if(h[i] & 1)
			ret[i] = ft[i];
		else
			ret[i] = st[i];
	}
	vector <int> num; num.clear();
	for(int i = 0; i < n; i++)
		num.pb(ret[i]);
	sort(all(num));
	num.resize(unique(all(num)) - num.begin());
	for(int i = 0; i < n; i++){
		ret[i] = lower_bound(all(num), ret[i]) - num.begin();
	}
	return ret;
}

int find_next_station(int s, int t, std::vector<int> c) {
	for(auto u : c) if(u == t)
		return t;
	sort(all(c));
	if(s == 0){
		int pt = upper_bound(all(c), t) - c.begin();
		return c[pt];
	}
	if(c.size() == 1)
		return c[0];
	if(s < c[0]){ // s is st
		int st = s, ft = c[int(c.size()) - 2];
		if(st > t || ft < t){
			return c.back(); // par
		}
		else{
			int pt = upper_bound(all(c), t) - c.begin();
			return c[pt];
		}
	}
	else{ // s is ft
		int ft = s, st = c[1];
		if(st >= t || ft < t)
			return c[0];
		int pt = upper_bound(all(c), t) - c.begin() - 1;
		return c[pt];
	}
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	390 ms	5428 KB	Output is correct
2	Correct	314 ms	5304 KB	Output is correct
3	Correct	596 ms	5408 KB	Output is correct
4	Correct	480 ms	5300 KB	Output is correct
5	Correct	427 ms	5280 KB	Output is correct
6	Correct	302 ms	5544 KB	Output is correct
7	Correct	313 ms	5408 KB	Output is correct
8	Correct	3 ms	5372 KB	Output is correct
9	Correct	4 ms	5364 KB	Output is correct
10	Correct	2 ms	5368 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	327 ms	5284 KB	Output is correct
2	Correct	342 ms	5448 KB	Output is correct
3	Correct	550 ms	5284 KB	Output is correct
4	Correct	404 ms	5292 KB	Output is correct
5	Correct	400 ms	5284 KB	Output is correct
6	Correct	309 ms	5300 KB	Output is correct

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	353 ms	5408 KB	Output is correct
2	Correct	302 ms	5424 KB	Output is correct
3	Correct	543 ms	5284 KB	Output is correct
4	Correct	388 ms	5280 KB	Output is correct
5	Correct	393 ms	5296 KB	Output is correct
6	Correct	283 ms	5420 KB	Output is correct
7	Correct	302 ms	5304 KB	Output is correct
8	Correct	4 ms	5364 KB	Output is correct
9	Correct	4 ms	5372 KB	Output is correct
10	Correct	2 ms	5364 KB	Output is correct
11	Correct	424 ms	5284 KB	Output is correct
12	Correct	342 ms	5420 KB	Output is correct
13	Correct	333 ms	5432 KB	Output is correct
14	Correct	263 ms	5280 KB	Output is correct
15	Correct	35 ms	5368 KB	Output is correct
16	Correct	56 ms	5316 KB	Output is correct
17	Correct	62 ms	5308 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	668 ms	5280 KB	Output is correct
2	Correct	434 ms	5284 KB	Output is correct
3	Correct	392 ms	5284 KB	Output is correct
4	Correct	3 ms	5372 KB	Output is correct
5	Correct	4 ms	5364 KB	Output is correct
6	Correct	2 ms	5340 KB	Output is correct
7	Correct	387 ms	5296 KB	Output is correct
8	Correct	565 ms	5284 KB	Output is correct
9	Correct	466 ms	5408 KB	Output is correct
10	Correct	410 ms	5284 KB	Output is correct
11	Correct	6 ms	5364 KB	Output is correct
12	Correct	5 ms	5372 KB	Output is correct
13	Correct	5 ms	5368 KB	Output is correct
14	Correct	4 ms	5364 KB	Output is correct
15	Correct	2 ms	5376 KB	Output is correct
16	Correct	375 ms	5280 KB	Output is correct
17	Correct	323 ms	5280 KB	Output is correct
18	Correct	299 ms	5284 KB	Output is correct
19	Correct	296 ms	5304 KB	Output is correct
20	Correct	345 ms	5280 KB	Output is correct

Subtask #5
61.0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	375 ms	5408 KB	Output is correct
2	Correct	267 ms	5412 KB	Output is correct
3	Correct	605 ms	5280 KB	Output is correct
4	Correct	509 ms	5296 KB	Output is correct
5	Correct	408 ms	5308 KB	Output is correct
6	Correct	327 ms	5412 KB	Output is correct
7	Correct	298 ms	5280 KB	Output is correct
8	Correct	3 ms	5364 KB	Output is correct
9	Correct	4 ms	5364 KB	Output is correct
10	Correct	2 ms	5364 KB	Output is correct
11	Correct	316 ms	5316 KB	Output is correct
12	Correct	374 ms	5296 KB	Output is correct
13	Correct	626 ms	5280 KB	Output is correct
14	Correct	483 ms	5292 KB	Output is correct
15	Correct	399 ms	5300 KB	Output is correct
16	Correct	301 ms	5368 KB	Output is correct
17	Correct	401 ms	5292 KB	Output is correct
18	Correct	303 ms	5308 KB	Output is correct
19	Correct	294 ms	5420 KB	Output is correct
20	Correct	331 ms	5296 KB	Output is correct
21	Correct	39 ms	5364 KB	Output is correct
22	Correct	47 ms	5368 KB	Output is correct
23	Correct	75 ms	5392 KB	Output is correct
24	Correct	5 ms	5364 KB	Output is correct
25	Correct	5 ms	5372 KB	Output is correct
26	Correct	5 ms	5360 KB	Output is correct
27	Correct	3 ms	5364 KB	Output is correct
28	Correct	2 ms	5372 KB	Output is correct
29	Correct	356 ms	5296 KB	Output is correct
30	Correct	365 ms	5296 KB	Output is correct
31	Correct	333 ms	5284 KB	Output is correct
32	Correct	321 ms	5296 KB	Output is correct
33	Correct	374 ms	5300 KB	Output is correct
34	Correct	231 ms	5416 KB	Output is correct
35	Correct	314 ms	5424 KB	Output is correct
36	Correct	310 ms	5436 KB	Output is correct
37	Correct	326 ms	5444 KB	Output is correct
38	Correct	327 ms	5428 KB	Output is correct
39	Correct	303 ms	5440 KB	Output is correct
40	Correct	318 ms	5452 KB	Output is correct
41	Correct	291 ms	5544 KB	Output is correct
42	Correct	48 ms	5364 KB	Output is correct
43	Correct	72 ms	5344 KB	Output is correct
44	Correct	92 ms	5432 KB	Output is correct
45	Correct	112 ms	5412 KB	Output is correct
46	Correct	206 ms	5292 KB	Output is correct
47	Correct	214 ms	5296 KB	Output is correct
48	Correct	46 ms	5472 KB	Output is correct
49	Correct	46 ms	5412 KB	Output is correct

Submission #824753

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 8.0 / 8.0

Subtask #3 16.0 / 16.0

Subtask #4 10.0 / 10.0

Subtask #5 61.0 / 61.0

Subtask #1
5.0 / 5.0

Subtask #2
8.0 / 8.0

Subtask #3
16.0 / 16.0

Subtask #4
10.0 / 10.0

Subtask #5
61.0 / 61.0