Submission #802701

#	Time	Username	Problem	Language	Result	Execution time	Memory
802701		SanguineChameleon	Through Another Maze Darkly (CCO21_day1problem3)	C++17	25 / 25	1945 ms	250160 KiB

Main

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int maxn = 8e5 + 20;
vector<int> adj[maxn];
int first[maxn];
vector<int> events[maxn];
vector<pair<int, int>> queries[maxn];
long long pref[maxn];
vector<int> tour;
int res[maxn];
int bit[maxn * 2];
int n, q;

void dfs1(int u, int par) {
	int pos = find(adj[u].begin(), adj[u].end(), par) - adj[u].begin();
	for (int i = 0; i < pos; i++) {
		first[adj[u][i]] = first[u];
		dfs1(adj[u][i], u);
	}
	for (int i = pos + 1; i < (int)adj[u].size(); i++) {
		first[adj[u][i]] = first[u] + 1;
		dfs1(adj[u][i], u);
	}
	if (par != -1) {
		rotate(adj[u].begin(), adj[u].begin() + pos, adj[u].end());
	}
}

void add(int u, int v, int t) {
	events[t].push_back(tour.size());
	tour.push_back(v);
}

void dfs2(int u) {
	for (int i = (u > 1); i < (int)adj[u].size(); i++) {
		add(u, adj[u][i], first[adj[u][i]]);
		dfs2(adj[u][i]);
		add(adj[u][i], u, first[adj[u][i]]);
	}
}

void update(int pos) {
	for (int i = pos; i <= n * 2 - 2; i += i & (-i)) {
		bit[i]++;
	}
}

int get(int pos) {
	int res = 0;
	for (int i = pos; i > 0; i -= i & (-i)) {
		res += bit[i];
	}
	return res;
}

int getk(int k) {
	int lt = 1;
	int rt = n * 2 - 2;
	while (lt <= rt) {
		int mt = (lt + rt) / 2;
		if (get(mt) >= k) {
			rt = mt - 1;
		}
		else {
			lt = mt + 1;
		}
	}
	return lt;
}

void just_do_it() {
	cin >> n >> q;
	for (int u = 1; u <= n; u++) {
		int deg;
		cin >> deg;
		adj[u].resize(deg);
		for (int i = 0; i < deg; i++) {
			cin >> adj[u][i];
		}
		if (deg > 1) {
			rotate(adj[u].begin(), adj[u].begin() + 1, adj[u].end());
		}
	}
	first[1] = 1;
	dfs1(1, -1);
	tour.push_back(-1);
	dfs2(1);
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		sum += events[i].size();
		pref[i] = pref[i - 1] + sum;
	}
	for (int i = 1; i <= q; i++) {
		long long k;
		cin >> k;
		int t = lower_bound(pref + 1, pref + n + 1, k) - pref;
		if (t == n + 1) {
			res[i] = tour[(k - pref[n] - 1) % (n * 2 - 2) + 1];
		}
		else {
			queries[t].emplace_back(i, k - pref[t - 1]);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (auto id: events[i]) {
			update(id);
		}
		for (auto q: queries[i]) {
			res[q.first] = tour[getk(q.second)];
		}
	}
	for (int i = 1; i <= q; i++) {
		cout << res[i] << '\n';
	}
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 12 / 12
• Subtask 4: 5 / 5