제출 #799585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
799585		QwertyPi	기지국 (IOI20_stations)	C++14	100 / 100	717 ms	776 KiB

stations

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

using namespace std;

const int MAXN = 1e3 + 11;
vector<int> G[MAXN];
int sz[MAXN], L[MAXN];

void dfs_prec(int v, int pa = -1){
	int _sz = 1;
	for(auto u : G[v]){
		if(u != pa){
			dfs_prec(u, v); _sz += sz[u];
		}
	}
	sz[v] = _sz;
}

void dfs_label(int v, int pa, int l, int r, bool large){
	L[v] = large ? r-- : l++;
	for(auto u : G[v]){
		if(u != pa){
			dfs_label(u, v, l, l + sz[u] - 1, !large); l += sz[u];
		}
	}
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	for(int i = 0; i < n; i++){
		G[i].clear();
	}
	for(int i = 0; i < n - 1; i++){
		G[u[i]].push_back(v[i]);
		G[v[i]].push_back(u[i]);
	}
	dfs_prec(0);
	dfs_label(0, -1, 0, n - 1, true);
	vector<int> labels(n);
	for(int i = 0; i < n; i++){
		labels[i] = L[i];
	}
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if(c.size() == 1) return c[0];
	sort(c.begin(), c.end());
	if(s < c[0]){
		for(int i = 0; i < (int) c.size() - 1; i++){
			if(c[i] >= t && t >= s) return c[i];
		}
		return c[(int) c.size() - 1];
	}else{
		for(int i = (int) c.size() - 1; i >= 1; i--){
			if(c[i] <= t && t <= s) return c[i];
		}
		return c[0];
	}
	return -1;
}

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