제출 #413537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413537		SuhaibSawalha1	기지국 (IOI20_stations)	C++17	39 / 100	1039 ms	732 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<vector<int>> adj;
vector<int> lab;
int cnt, inc;
 
void dfs (int u, int p = -1) {
	for (int v : adj[u]) {
		if (v ^ p) {
			dfs(v, u);
		}
	}
	lab[u] = cnt++;
}
 
void dfs2 (int u, int p, int lb) {
	lab[u] = lb;
	for (int v : adj[u]) {
		if (v ^ p) {
			dfs2(v, u, lb + 1);
		}
	}
}

void dfs3 (int u = 0, int p = -1, int lb = 0) {
	lab[u] = lb += pow(10, inc--);
	for (int v : adj[u]) {
		if (v ^ p) {
			dfs3(v, u, lb);
		}
	}
}
 
bool subtask2 () {
	for (int i = 0; i < (int)adj.size(); ++i) {
		vector<int> y{(i - 1) / 2, 2 * i + 1, 2 * i + 2};
		if (!i) {
			y.erase(y.begin());
		}
		sort(adj[i].begin(), adj[i].end());
		while (y.size() > adj[i].size()) {
			y.pop_back();
		}
		if (y != adj[i]) {
			return 0;
		}
	}
	return 1;
}
 
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	adj.assign(n, {});
	lab.resize(n);
	cnt = 0;
	for (int i = 0; i < n - 1; ++i) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	if (subtask2()) {
		iota(lab.begin(), lab.end(), 0);
		return lab;
	}
	if (all_of(adj.begin(), adj.end(), [](auto &e) {return e.size() < 3;})) {
		for (int i = 0; i < n; ++i) {
			if (adj[i].size() == 1) {
				dfs(i);
				break;
			}
		}
		return lab;
	}
	if (k == 1e6) {
		array<int, 2> p {0};
		for (int i = 0; i < n; ++i) {
			p = max(p, {(int)adj[i].size(), i});
		}
		int lb = 1e3;
		lab[p[1]] = lb;
		for (int v : adj[p[1]]) {
			lb += 1e3;
			dfs2(v, p[1], lb);
		}
		return lab;
	}
	inc = 7;
	dfs3();
	return lab;
}

vector<int> go (int v) {
	string s = to_string(v);
	vector<int> a;
	for (int i = 7; ~i; --i) {
		if (s[7 - i] == '1') {
			a.push_back(pow(10, i));
		}
	}
	return a;
}

int first (vector<int> &a, vector<int> &b) {
	for (int i = 0; i < (int)min(a.size(), b.size()); ++i) {
		if (a[i] != b[i]) {
			return 0;
		}
	}
	if (a.size() < b.size()) {
		return b[a.size()];
	}
	return 0;
}
 
int find_next_station(int s, int t, vector<int> c) {
	if (c.size() == 1) {
		return c[0];
	}
	int o = 1e7;
	if (s >= o) {
		vector<int> a = go(s), b = go(t);
		if (int v = first(a, b)) {
			return s + v;
		}
		return s - a.back();
	}
	o = 1e3;
	if (s >= o) {
		if (s / o == t / o) {
			return s - (t < s) + (t > s);
		}
		return s == o ? t / o * o : s % o ? s - 1 : o;	
	}
	sort(c.begin(), c.end());
	vector<int> y{(s - 1) / 2, 2 * s + 1, 2 * s + 2};
	if (!s) {
		y.erase(y.begin());
	}
	while (y.size() > c.size()) {
		y.pop_back();
	}
	if (y != c) {
		return s - (t < s) + (t > s);
	}
	int e = t;
	while (e) {
		int p = (e - 1) / 2;
		if (p == s) {
			return e;
		}
		e = p;
	}
	return (s - 1) / 2;
}

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