Submission #1234179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234179		SpyrosAliv	Stations (IOI20_stations)	C++20	21 / 100	304 ms	576 KiB

stations

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

vector<vector<int>> tree;
vector<int> labels;
int n;

void dfs(int node, int mult, int prev, int d = 1) {
	labels[node] = 1000 * mult + d;
	for (auto next: tree[node]) {
		if (next == prev) continue;
		dfs(next, mult, node, d+1);
	}
}

vector<int> label(int N, int k, vector<int> u, vector<int> v) {
	n = N;
	int center = 0;
	tree.clear();
	tree.resize(n);
	labels.clear();
	labels.assign(n, -1);
	for (int i = 0; i < n-1; i++) {
		tree[u[i]].push_back(v[i]);
		tree[v[i]].push_back(u[i]);
	}
	for (int i = 1; i < n; i++) {
		if (tree[i].size() == 1) center = i;
	}
	for (int i = 0; i < n; i++) {
		if (tree[i].size() > 2) center = i;
	}
	labels[center] = 0;
	int mult = 0;
	for (auto next: tree[center]) {
		dfs(next, mult, center);
		mult++;
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	int ch = c.size();
	sort(c.begin(), c.end());
	if (ch == 1) return c[0];
	if (ch == 2) {
		int compS = (s - 1) / 1000;
		int compT = (t - 1) / 1000;
		if (compT != compS) {
			return c[0];
		}
		else {
			return c[s < t];
		}
	}
	else {
		int compT = (t - 1) / 1000;
		for (auto x: c) {
			int compC = (x - 1) / 1000;
			if (compC == compT) return x;
		}
		assert(false);
	}
}

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