Submission #1229190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229190		marsasgrg	Stations (IOI20_stations)	C++20	5 / 100	305 ms	492 KiB

stations

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


std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	vector<int> labels(n);
	vector<vector<int>> adj(n);
	for (int i = 0; i < n - 1; i++) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	int oneNeighbor = 0;
	int counter = 0;
	for (int i = 0; i < n; i++) {
		if (adj[i].size() == 1) {
			oneNeighbor = i;
			break;
		}
	}
	stack<int> dfs;
	dfs.push(oneNeighbor);
	vector visited(n, false);
	while (!dfs.empty()) {

		const int x = dfs.top();
		dfs.pop();
		if (visited[x]) continue;
		visited[x] = true;
		labels[x] = counter;
		counter++;
		for (int y : adj[x]) {
			if (!visited[y]) dfs.push(y);
		}
	}


	return labels;
}

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

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