oj.uz

Submission #835336

# Submission time Handle Problem Language Result Execution time Memory
835336 2023-08-23T13:21:32 Z welleyth Stations (IOI20_stations) C++17
100 / 100
 767 ms 1180 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int N = (int)1e3;

int tin[N],tout[N];
int timer = 0;

vector<int> g[N];
int id[N];
int d[N];
int c = 0;
vector<int> labels;

mt19937 rnd(time(nullptr));

int sz[N];
vector<int> values;

void dfs(int v,int pr = -1){
	tin[v] = timer++;
	for(auto& to : g[v]){
		if(to == pr) continue;
		if(id[v] == 0)
			id[to] = ++c;
		else
			id[to] = id[v];
		d[to] = d[v] + 1;
		dfs(to,v);
	}
	tout[v] = timer++;
	if(d[v] % 2 == 0){
		// labels[v] = (tin[v] << 1);
		values.push_back(tin[v]);
	} else {
		// labels[v] = ;
		values.push_back(tout[v]);
	}
	return;
}

void dfs1(int v,int pr = -1){
	sz[v] = 1;
	for(auto& to : g[v]){
		if(to == pr) continue;
		dfs1(to,v);
		sz[v] += sz[to];
	}
	return;
}

int find_centroid(int v,int S){
	for(auto& to : g[v]){
		if(sz[to] > sz[v]) continue;
		if(sz[to] > S/2) return find_centroid(to,S);
	}
	return v;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	for(int i = 0; i < n; i++) g[i].clear();
	timer = 0;
	labels.clear();
	labels.resize(n);
	memset(id,0,sizeof id);
	memset(d,0,sizeof d);
	c = 0;
	for(int i = 0; i < n-1; i++){
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs1(0);
	int root = find_centroid(0,n);
	values.clear();
	d[root] = 0;
	dfs(root);
	sort(values.begin(),values.end());
	values.erase(unique(values.begin(),values.end()),values.end());
	for(int i = 0; i < n; i++){
		if(d[i] % 2 == 0){
			labels[i] = lower_bound(values.begin(),values.end(),tin[i]) - values.begin();
		} else {
			labels[i] = lower_bound(values.begin(),values.end(),tout[i]) - values.begin();
		}
	}
	return labels;
}

bool upper(int a,int b){
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int find_next_station(int s, int t, std::vector<int> c) {
	int tinS = 2*N, toutS = -1, tinT = 2*N, toutT = -1;
	bool isToutS = true;
	for(auto& to : c){
		isToutS &= s > to; 
	}
	if(isToutS)
		toutS = s;
	else
		tinS = s;
	tinT = toutT = t;
	int pr = -1;
	for(auto& to : c){
		int in,out;
		if(!isToutS){
			out = to;
			if(pr == -1 || out > pr)
				pr = to;
		}
		else{
			in = to;
			if(pr == -1 || in < pr)
				pr = to;
		}
	}

	int go = -1;

	for(auto& to : c){
		// if(to == pr) continue;
		int in,out;
		if(!isToutS){
			out = to;
			if(tinT < tinS)
				return pr;
			if(out >= tinT && (go == -1 || out < go))
				go = to;
		}
		else{
			in = to;
			if(toutT > toutS)
				return pr;
			if(in <= toutT && (go == -1 || in > go))
				go = to;
		}
	}
	if(go == -1)
		return pr;

	return go;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 804 KB Output is correct
2 Correct 439 ms 848 KB Output is correct
3 Correct 639 ms 668 KB Output is correct
4 Correct 471 ms 672 KB Output is correct
5 Correct 381 ms 740 KB Output is correct
6 Correct 292 ms 800 KB Output is correct
7 Correct 376 ms 672 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 672 KB Output is correct
2 Correct 371 ms 672 KB Output is correct
3 Correct 643 ms 672 KB Output is correct
4 Correct 540 ms 672 KB Output is correct
5 Correct 563 ms 672 KB Output is correct
6 Correct 376 ms 672 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 804 KB Output is correct
2 Correct 291 ms 800 KB Output is correct
3 Correct 639 ms 692 KB Output is correct
4 Correct 394 ms 672 KB Output is correct
5 Correct 553 ms 680 KB Output is correct
6 Correct 297 ms 1180 KB Output is correct
7 Correct 360 ms 740 KB Output is correct
8 Correct 2 ms 744 KB Output is correct
9 Correct 4 ms 752 KB Output is correct
10 Correct 0 ms 756 KB Output is correct
11 Correct 412 ms 672 KB Output is correct
12 Correct 416 ms 800 KB Output is correct
13 Correct 313 ms 1040 KB Output is correct
14 Correct 454 ms 672 KB Output is correct
15 Correct 35 ms 748 KB Output is correct
16 Correct 38 ms 688 KB Output is correct
17 Correct 95 ms 676 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 676 KB Output is correct
2 Correct 462 ms 672 KB Output is correct
3 Correct 565 ms 672 KB Output is correct
4 Correct 1 ms 756 KB Output is correct
5 Correct 4 ms 748 KB Output is correct
6 Correct 0 ms 756 KB Output is correct
7 Correct 450 ms 672 KB Output is correct
8 Correct 696 ms 548 KB Output is correct
9 Correct 513 ms 672 KB Output is correct
10 Correct 379 ms 548 KB Output is correct
11 Correct 4 ms 756 KB Output is correct
12 Correct 2 ms 756 KB Output is correct
13 Correct 2 ms 756 KB Output is correct
14 Correct 3 ms 756 KB Output is correct
15 Correct 1 ms 756 KB Output is correct
16 Correct 451 ms 676 KB Output is correct
17 Correct 385 ms 672 KB Output is correct
18 Correct 412 ms 672 KB Output is correct
19 Correct 420 ms 672 KB Output is correct
20 Correct 330 ms 676 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 804 KB Output is correct
2 Correct 307 ms 804 KB Output is correct
3 Correct 745 ms 672 KB Output is correct
4 Correct 379 ms 672 KB Output is correct
5 Correct 542 ms 672 KB Output is correct
6 Correct 322 ms 944 KB Output is correct
7 Correct 381 ms 700 KB Output is correct
8 Correct 3 ms 840 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 330 ms 548 KB Output is correct
12 Correct 326 ms 748 KB Output is correct
13 Correct 767 ms 736 KB Output is correct
14 Correct 525 ms 672 KB Output is correct
15 Correct 525 ms 668 KB Output is correct
16 Correct 289 ms 672 KB Output is correct
17 Correct 399 ms 740 KB Output is correct
18 Correct 314 ms 740 KB Output is correct
19 Correct 406 ms 800 KB Output is correct
20 Correct 303 ms 672 KB Output is correct
21 Correct 52 ms 748 KB Output is correct
22 Correct 59 ms 720 KB Output is correct
23 Correct 83 ms 676 KB Output is correct
24 Correct 5 ms 748 KB Output is correct
25 Correct 2 ms 748 KB Output is correct
26 Correct 3 ms 748 KB Output is correct
27 Correct 2 ms 748 KB Output is correct
28 Correct 2 ms 748 KB Output is correct
29 Correct 383 ms 672 KB Output is correct
30 Correct 495 ms 676 KB Output is correct
31 Correct 385 ms 676 KB Output is correct
32 Correct 423 ms 672 KB Output is correct
33 Correct 385 ms 676 KB Output is correct
34 Correct 261 ms 780 KB Output is correct
35 Correct 401 ms 796 KB Output is correct
36 Correct 449 ms 928 KB Output is correct
37 Correct 441 ms 676 KB Output is correct
38 Correct 436 ms 668 KB Output is correct
39 Correct 398 ms 792 KB Output is correct
40 Correct 364 ms 696 KB Output is correct
41 Correct 387 ms 724 KB Output is correct
42 Correct 53 ms 700 KB Output is correct
43 Correct 102 ms 748 KB Output is correct
44 Correct 120 ms 676 KB Output is correct
45 Correct 147 ms 768 KB Output is correct
46 Correct 215 ms 752 KB Output is correct
47 Correct 238 ms 672 KB Output is correct
48 Correct 40 ms 752 KB Output is correct
49 Correct 54 ms 964 KB Output is correct