제출 #1234184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234184		SpyrosAliv	Stations (IOI20_stations)	C++20	36.23 / 100	313 ms	616 KiB

stations

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

vector<vector<int>> tree;
vector<int> labels, tin, sub;
int n, t;

void dfs(int node, int par) {
	tin[node] = t++;
	sub[node] = 1;
	for (auto next: tree[node]) {
		if (next == par) continue;
		dfs(next, node);
		sub[node] += sub[next];
	}
}

vector<int> label(int N, int k, vector<int> u, vector<int> v) {
	n = N;
	tree.clear();
	tree.resize(n);
	labels.clear();
	labels.assign(n, -1);
	t = 0;
	tin.assign(n, 0);
	sub.assign(n, 0);
	for (int i = 0; i < n-1; i++) {
		tree[u[i]].push_back(v[i]);
		tree[v[i]].push_back(u[i]);
	}
	dfs(0, 0);
	for (int i = 0; i < n; i++) {
		int ord = tin[i];
		int tot = sub[i];
		int val = 0;
		for (int i = 0; i < 10; i++) {
			if ((ord >> i) & 1) val |= (1 << i);
		}
		for (int i = 10; i < 20; i++) {
			int j = i - 10;
			if ((tot >> j) & 1) val |= (1 << i);
		}
		labels[i] = val;
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	int ch = c.size();
	int par = -1;
	int need = 0;
	for (int i = 0; i < 10; i++) {
		if ((t >> i) & 1) {
			need |= (1 << i);
		}
	}
	int ordCurr = 0;
	for (int i = 0; i < 10; i++) {
		if ((s >> i) & 1) {
			ordCurr |= (1 << i);
		}
	}
	for (auto next: c) {
		int ord = 0, sub = 0;
		for (int i = 0; i < 10; i++) {
			if ((next >> i) & 1) {
				ord |= (1 << i);
			}
		}
		for (int i = 10; i < 20; i++) {
			if ((next >> i) & 1) {
				sub |= (1 << (i - 10));
			}
		}
		if (ord < ordCurr) {
			par = next;
			continue;
		}
		int l = ord;
		int r = ord + sub - 1;
		if (need >= l && need <= r) return next;
	}
	return par;
}

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