Submission #1266136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266136		rreshi	Stations (IOI20_stations)	C++20	52.32 / 100	308 ms	584 KiB

stations

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

#include <bits/stdc++.h>
#define FOR(i, s, e) for (int i = s; i < e; i++)
using namespace std;

const int MAX = 1000;
std::vector<int> label(int N, int K, std::vector<int> U, std::vector<int> V) {
	vector<vector<int>> graph(N);
	FOR(i, 0, N-1) graph[U[i]].push_back(V[i]), graph[V[i]].push_back(U[i]);

	int t = 0;
	vector<int> tin(N, -1), sz(N);
	function<void(int)> dfs = [&](int cur) {
		tin[cur] = t++;
		sz[cur] = 1;
		for (int nxt: graph[cur]) {
			if (tin[nxt] != -1) continue;
			dfs(nxt);
			sz[cur] += sz[nxt];
		}
	}; dfs(0);

	vector<int> label(N); 
	FOR(i, 0, N) label[i] = tin[i]*MAX+(sz[i]-1) +1;
	return label;
}

int find_next_station(int s, int t, std::vector<int> c) {
	s--, t--;
	int ssz = s%MAX+1, stin = s/MAX;
	int tsz = t%MAX+1, ttin = t/MAX;
	int p = -1, a = -1;
	for (int n: c) {
		n--;
		int nsz = n%MAX+1, ntin = n/MAX;
		if (nsz > ssz) p = n;
		else if (ntin <= ttin && ttin < ntin+nsz) a = n;
	} 
	if (a != -1) return a+1;
	return p+1;
}

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