제출 #1234426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234426		oscarsierra12	기지국 (IOI20_stations)	C++20	52.32 / 100	314 ms	592 KiB

stations

#include "stations.h"
#include<bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
#define pb push_back

vi labels(1005);
#define sz(u) (int(u.size()))
int cnt = 0;

int dfs(int no, int fat, vvi &ed){
	int label = cnt;
	cnt++;
	int subtreesz = 1;
	for(auto e:ed[no]){
		if(e == fat)continue;
		subtreesz += dfs(e, no, ed);
	}
	label *= 1000;
	label += (subtreesz-1);
	labels[no] = label;
	return subtreesz;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
  cnt = 0;
	vvi ed(n+1);
	for(int i = 0; i < sz(u); ++i){
		ed[u[i]].pb(v[i]);
		ed[v[i]].pb(u[i]);
	}
	dfs(0, -1, ed);
	vi ans;
	for(int i = 0; i < n; ++i){
		ans.pb(labels[i]);
	}
	return ans;
}

int find_next_station(int s, int t, std::vector<int> c) {
	int source = s / 1000;
	int target = t / 1000;
	int ssize = s % 1000;
	if( (target < source) || (target > (source + (ssize))) ){
		for(auto e:c){
			int node = e/1000;
			if(node < source){
				return e;
			}
		}
		return c[0];
	}else{
		for(auto e:c){
			int node = e / 1000;
			int nodesize = e % 1000;
			if(node < source)continue;
			if(target >= node && target <= (node + nodesize)){
				return e;
			}
		}
		return c[0];
	}
}

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