Submission #1292664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292664		julia_08	기지국 (IOI20_stations)	C++20	36.23 / 100	391 ms	560 KiB

stations

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

using namespace std;

const int MAXN = 1e3 + 10;

int pre[MAXN], pos[MAXN];

vector<int> adj[MAXN];

int t = 0;

void dfs(int v, int p){

	pre[v] = ++t;

	for(auto u : adj[v]){
		if(u != p){
			dfs(u, v);
		}
	}

	pos[v] = t;

}

vector<int> label(int n, int k, vector<int> u, vector<int> v){

	t = 0;

	for(int i=0; i<n; i++) adj[i].clear();

	vector<int> labels(n);

	for(int i=0; i<(n - 1); i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}

	dfs(0, 0);

	for(int i=0; i<n; i++) labels[i] = pre[i] + (pos[i] << 10);

	return labels;

}

int find_pai(int v, int pre_v, int pos_v, vector<int> &c){

	for(auto u : c){
		int pre_u = u % (1 << 10), pos_u = u - pre_u;
		if(pre_u <= pre_v && pos_v <= pos_u) return u;
	}

	return 0;

}

int find_next_station(int s, int t, vector<int> c){

	// alguns casos

	int pre_s = s % (1 << 10), pos_s = s - pre_s;

	int pre_t = t % (1 << 10), pos_t = t - pre_t;

	int pai = find_pai(s, pre_s, pos_s, c);

	// se t contido em s
	if(pre_s <= pre_t && pos_t <= pos_s){

		// acha o filho que contem t
		for(auto x : c){

			if(x == pai) continue;

			int cur_pre = x % (1 << 10), cur_pos = x - cur_pre;
			if(cur_pre <= pre_t && pos_t <= cur_pos) return x;

		}

	}

	return pai;

}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 10 / 10
• Subtask 5: 26.2265 / 61