제출 #1042590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1042590		AmirAli_H1	기지국 (IOI20_stations)	C++17	100 / 100	554 ms	1332 KiB

stations

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2000 + 4;

int n, k;
vector<int> adj[maxn];
int h[maxn], timer;
vector<int> A;

void dfs(int v, int p = -1) {
	if (h[v] % 2 == 0) A[v] = timer++;
	for (int u : adj[v]) {
		if (u == p) continue;
		h[u] = h[v] + 1;
		dfs(u, v);
	}
	if (h[v] % 2 == 1) A[v] = timer++;
}

vector<int> label(int Nx, int Kx, vector<int> ux, vector<int> vx) {
	n = Nx; k = Kx;
	for (int i = 0; i < n; i++) adj[i].clear();
	for (int i = 0; i < n - 1; i++) {
		int u = ux[i], v = vx[i];
		adj[u].pb(v); adj[v].pb(u);
	}
	A.clear(); A.resize(n);
	timer = 0; dfs(0);
	return A;
}

int find_next_station(int s, int t, vector<int> ls) {
	if (len(ls) == 1) return ls[0];
	
	sort(all(ls));
	if (ls[0] > s) {
		int p = ls.back(); ls.pop_back();
		int l = s + 1;
		for (int r : ls) {
			if (t >= l && t <= r) return r;
			l = r + 1;
		}
		return p;
	}
	else {
		reverse(all(ls));
		int p = ls.back(); ls.pop_back();
		int r = s - 1;
		for (int l : ls) {
			if (t >= l && t <= r) return l;
			r = l - 1;
		}
		return p;
	}
}

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