Submission #835826

#	Time	Username	Problem	Language	Result	Execution time	Memory
835826		JustAmethyst	Stations (IOI20_stations)	C++17	0 / 100	13 ms	676 KiB

stations

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

const int N = 1000;
vector<int> edges[N];
vector<int> tin(N), tout(N);
int t1, t2;

void dfs(int x, int p) {
	int y;
	tin[x] = t1;
	++t1;

	while (!edges[x].empty()) {
		y = edges[x].back();
		edges[x].pop_back();
		if (y != p) {
			dfs(y, x);
		}
	}
	tout[x] = t2;
	++t2;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	t1 = 0, t2 = 0;
	// for (int i = 0; i < n; i++) {
	// 	edges[i].clear();
	// }

	for (int i = 0; i < n-1; ++i) {
		edges[u[i]].push_back(v[i]);
		edges[v[i]].push_back(u[i]);
	}

	dfs(0, -1);
	for (int i = 0; i < n; ++i) {
		labels[i] = tin[i]*1000 + tout[i];
	}
	return labels;
}

int find_next_station(int s, int e, vector<int> c) {
	int sin = s/1000, sout = s % 1000;
	int ein = e/1000, eout = e % 1000;
	cout << sin << " " << sout << " " << ein << "\n";
	if (ein < sin) {
		for (int x : c) {
			if ((x/1000) <= sin) {
				return x;
			}
		}
	}
	for (int x : c) {
		if ((x/1000) <= ein && (x%1000) >= eout) {
			return x;
		}
	}

	return c[0];
}


// int main() {
// 	vector<int> labels = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
// 	for (auto x : labels) {
// 		cout << x << " ";
// 		cout << "\n";
// 	}

// 	labels = label(6, 10, {0, 1, 1, 3, 3}, {1, 2, 3, 4, 5});
// 	for (auto x : labels) {
// 		cout << x << " ";
// 		cout << "\n";
// 	}

// 	cout << "\n";
// 	cout << find_next_station(2001, 3000, {3000, 1003}) << "\n";
// }

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