Submission #457967

#	Time	Username	Problem	Language	Result	Execution time	Memory
457967		rainboy	기지국 (IOI20_stations)	C++17	100 / 100	1264 ms	55532 KiB

stations

#include "stations.h"
#include <vector>

using namespace std;
typedef vector<int> vi;

const int N = 1000;

void dfs(vector<vi> ej, vi &ta, vi &tb, int p, int i, int d, int &time) {
	if (d % 2 == 0)
		ta[i] = time++;
	for (int j : ej[i])
		if (j != p)
			dfs(ej, ta, tb, i, j, d + 1, time);
	if (d % 2 == 1)
		ta[i] = time++;
}

vi label(int n, int k, vi uu, vi vv) {
	vector<vi> ej(n);
	vi ta(n, 0), tb(n, 0), labels(n, 0);
	int h, i, time;

	for (h = 0; h < n - 1; h++) {
		ej[uu[h]].push_back(vv[h]);
		ej[vv[h]].push_back(uu[h]);
	}
	time = 0, dfs(ej, ta, tb, -1, 0, 0, time);
	for (i = 0; i < n; i++)
		labels[i] = ta[i];
	return labels;
}

int find_next_station(int s, int t, vi cc) {
	int m = cc.size(), h;

	if (s < cc[0]) {
		for (h = 0; h < m - 1; h++)
			if ((h == 0 ? s : cc[h - 1]) < t && t <= cc[h])
				break;
	} else {
		for (h = m - 1; h > 0; h--)
			if ((h + 1 == m ? s : cc[h + 1]) > t && t >= cc[h])
				break;
	}
	return cc[h];
}

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