제출 #1229229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229229		Adomas08	기지국 (IOI20_stations)	C++20	100 / 100	305 ms	800 KiB

stations

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

using namespace std;

int cur = 0; 
int parent[1000], secparent[1000];
vector<int> children[1000];
vector<int> secchildren[1000];
vector <int> adj[1000];
void dfs(int s, vector<int> &labels, vector <bool> visited){
	labels[s] = cur;
	cur++;
	vector <int> v;
	for (auto u : children[s]){
		for (auto v : children[u]){
			dfs(v, labels, visited);
		}
		labels[u] = cur;
		cur++;
	}
}


std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	for (int i = 0; i < n; i++){
		parent[i] = 0;
		secparent[i] = 0;
		cur = 0;
		children[i].clear();
		secchildren[i].clear();
		adj[i].clear();
	}
	std::vector<int> labels(n);
	vector <bool> visited(n, 0);
	for (int i = 0; i < u.size(); i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	queue <int> q;
	q.push(0);
	bool visit[n];
	for (int i = 0; i < n; i++) visit[i] = 0; 
	parent[0] = 0;
	while (!q.empty()){
		int s = q.front();
		q.pop();
		visit[s] = 1;
		for (auto u : adj[s]){
			if (!visit[u]){
				q.push(u);
				parent[u] = s;
				children[s].push_back(u);
			}
		}
	}
	for (int i = 1; i < n; i++){
		if (children[i].size() != 0){
			for (auto u : children[i]){
				secparent[u] = parent[i];
				secchildren[parent[i]].push_back(u);
			}
		}
	}
	dfs(0, labels, visited);
	return labels;
}

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

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