Submission #388391

#	Time	Username	Problem	Language	Result	Execution time	Memory
388391		JimmyZJX	Stations (IOI20_stations)	C++14	0 / 100	2 ms	584 KiB

stations

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>

using namespace std;

typedef long long LL;
typedef vector<int> Vi;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;

#define forR(i, n) for (int i = 0; i < (n); i++)

Vb visited(1003, false);
Vii nbs(1003);
int l = 0;

Vi labels;
void dfs(int x, int mode) { // 0: start, 1: end
	visited[x] = true;
	if (mode == 0) labels[x] = l++;

	for (int nb : nbs[x]) {
		if (visited[nb]) continue;
		dfs(nb, 1 - mode);
	}

	if (mode == 1) labels[x] = l++;
}

Vi label(int n, int k, Vi u, Vi v) {
	forR(i, n - 1) {
		nbs[u[i]].push_back(v[i]);
		nbs[v[i]].push_back(u[i]);
	}

	labels = Vi(n);
	dfs(0, 0);
	assert(l == n);

	return labels;
}

int find_next_station(int s, int t, Vi c) {
	if (s < c[0]) {
		// s.mode == 0
		int start = s;
		for (int end : c) {
			if (t >= start && t <= end) return end;
		}
		return c.back();
	} else {
		// s.mode == 1
		int end = s;
		for (auto it = c.rbegin(); it != c.rend(); it++) {
			int start = *it;
			if (t >= start && t <= end) return start;
		}
		return c[0];
	}
}

#ifdef TEST_LOCAL
int main() {
	auto lbs = label(5, 10, Vi{ 0, 1, 1, 2 }, Vi{ 1, 2, 3, 4 });

	return 0;
}
#endif

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