Submission #609732

#	Time	Username	Problem	Language	Result	Execution time	Memory
609732		penguinhacker	Stations (IOI20_stations)	C++17	0 / 100	841 ms	804 KiB

stations

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

const int mxN=1000;
int n, d[mxN], anc[mxN][10];
vector<int> adj[mxN];

void dfs(int u=0) {
	for (int i=1; i<10; ++i)
		anc[u][i]=anc[anc[u][i-1]][i-1];
	for (int v : adj[u])
		if (v!=anc[u][0]) {
			d[v]=d[u]+1;
			anc[v][0]=u;
			dfs(v);
		}
}

int lca(int u, int v) {
	if (d[u]>d[v])
		swap(u, v);
	for (int i=9; ~i; --i)
		if (d[v]-(1<<i)>=d[u])
			v=anc[v][i];
	if (u==v)
		return u;
	for (int i=9; ~i; --i)
		if (anc[u][i]^anc[v][i])
			u=anc[u][i], v=anc[v][i];
	return anc[u][0];
}

int dist(int u, int v) {
	return d[u]+d[v]-2*d[lca(u, v)];
}

vector<int> label(int _n, int _k, vector<int> u, vector<int> v) {
	n=_n;
	for (int i=0; i<n; ++i)
		adj[i].clear();
	for (int i=0; i<n-1; i++) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	dfs();
	vector<int> labels(n);
	iota(labels.begin(), labels.end(), 0);
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	int st=dist(s, t);
	//cout << s << " " << t << " " << st << endl;
	for (int i : c)
		if (dist(s, i)+dist(t, i)==st) {
			//cout << i << " " << dist(s, i) << " " << dist(t, i) << endl;
			return i;
		}
	assert(0);
	return -1;
}

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