Submission #1292765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292765		kahoul	Stations (IOI20_stations)	C++20	5 / 100	396 ms	488 KiB

stations

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

const int maxn = 1003;
vector<int> rel[maxn];

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	for (int i = 0; i < n; i++) {
		rel[i].clear();
	}
	
	vector<int> labels(n, -1);
	for (int i = 0; i < n - 1; i++) {
		rel[u[i]].push_back(v[i]);
		rel[v[i]].push_back(u[i]);
	}
	deque<int> q;
	for (int i = 0; i < n; i++) {
		if (rel[i].size() == 1) {
			q.push_back(i);
		}
	}
	q.pop_back();
	int t = 0;

	while (!q.empty()) {
		int u = q.front();
		q.pop_front();

		if (labels[u] != -1) continue;
		labels[u] = t++;

		for (auto v : rel[u]) {
			if (labels[v] != -1) continue;
			q.push_back(v);
		}
	}

	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	if (t == s) return s;
	if (t < s) return s - 1;
	return s + 1;
}

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