Submission #1292881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292881		gustavo_d	Stations (IOI20_stations)	C++20	100 / 100	401 ms	568 KiB

stations

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

const int MAXN = 1000;

int tin[MAXN], tout[MAXN], depth[MAXN]; int t = 0;
vector<int> adj[MAXN];
vector<tuple<int, int, int>> subs;

void dfs(int v, int pai) {
	// assert (t <= 10000);
	// cerr << v << endl;
	tin[v] = ((depth[v] & 1) == 0 ? t++ : t);
	for (int viz : adj[v]) {
		if (viz == pai) continue;
		depth[viz] = depth[v] + 1;
		dfs(viz, v);
	}
	tout[v] = (depth[v] & 1) ? t++ : t;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	// cerr << "here" << endl;
	for (int i=0; i<n; i++) {
		adj[i].clear();
		t = 0;
	}
	for (int i=0; i<n-1; i++) {
		int a = u[i], b = v[i];
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	dfs(0, -1);

	vector<int> labels(n);
	for (int i = 0; i < n; i++) {
		labels[i] = (depth[i] & 1) ? tout[i] : tin[i];
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	for (int viz : c) {
		if (viz == t) return viz;
	}
	bool hasTin = s < c[0];
	int pai = -1;
	subs.clear();
	if (hasTin) {
		pai = (s == 0 ? -1 : c.back());
		int l = s+1;
		for (int viz : c) {
			if (viz == pai) continue;
			subs.emplace_back(viz, l, viz);
			l = viz+1;
		}
	} else {
		pai = c[0];
		reverse(c.begin(), c.end());
		int r = s-1;
		for (int viz : c) {
			if (viz == pai) continue;
			subs.emplace_back(viz, viz, r);
			r = viz-1;
		}
	}

	for (auto [viz, l, r] : subs) {
		if (l <= t and t <= r) return viz;
	}

	return pai;
}

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