oj.uz

답안 #802701

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
802701 2023-08-02T13:30:23 Z SanguineChameleon Through Another Maze Darkly (CCO21_day1problem3) C++17
25 / 25
 1945 ms 250160 KB 
#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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 56664 KB Output is correct
2 Correct 37 ms 58828 KB Output is correct
3 Correct 126 ms 78840 KB Output is correct
4 Correct 789 ms 223964 KB Output is correct
5 Correct 1207 ms 250160 KB Output is correct
6 Correct 1319 ms 237628 KB Output is correct
7 Correct 355 ms 96164 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 56684 KB Output is correct
2 Correct 28 ms 56704 KB Output is correct
3 Correct 30 ms 56872 KB Output is correct
4 Correct 30 ms 56908 KB Output is correct
5 Correct 32 ms 56968 KB Output is correct
6 Correct 31 ms 56820 KB Output is correct
7 Correct 30 ms 56916 KB Output is correct
8 Correct 30 ms 56836 KB Output is correct
9 Correct 30 ms 56908 KB Output is correct
10 Correct 31 ms 57024 KB Output is correct
11 Correct 30 ms 56956 KB Output is correct
12 Correct 31 ms 57136 KB Output is correct
13 Correct 30 ms 57044 KB Output is correct
14 Correct 30 ms 57032 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 57812 KB Output is correct
2 Correct 49 ms 62656 KB Output is correct
3 Correct 85 ms 69932 KB Output is correct
4 Correct 64 ms 65600 KB Output is correct
5 Correct 532 ms 126908 KB Output is correct
6 Correct 596 ms 125524 KB Output is correct
7 Correct 620 ms 125840 KB Output is correct
8 Correct 676 ms 132636 KB Output is correct
9 Correct 870 ms 161496 KB Output is correct
10 Correct 1040 ms 175972 KB Output is correct
11 Correct 361 ms 216044 KB Output is correct
12 Correct 355 ms 207732 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 56664 KB Output is correct
2 Correct 37 ms 58828 KB Output is correct
3 Correct 126 ms 78840 KB Output is correct
4 Correct 789 ms 223964 KB Output is correct
5 Correct 1207 ms 250160 KB Output is correct
6 Correct 1319 ms 237628 KB Output is correct
7 Correct 355 ms 96164 KB Output is correct
8 Correct 28 ms 56684 KB Output is correct
9 Correct 28 ms 56704 KB Output is correct
10 Correct 30 ms 56872 KB Output is correct
11 Correct 30 ms 56908 KB Output is correct
12 Correct 32 ms 56968 KB Output is correct
13 Correct 31 ms 56820 KB Output is correct
14 Correct 30 ms 56916 KB Output is correct
15 Correct 30 ms 56836 KB Output is correct
16 Correct 30 ms 56908 KB Output is correct
17 Correct 31 ms 57024 KB Output is correct
18 Correct 30 ms 56956 KB Output is correct
19 Correct 31 ms 57136 KB Output is correct
20 Correct 30 ms 57044 KB Output is correct
21 Correct 30 ms 57032 KB Output is correct
22 Correct 34 ms 57812 KB Output is correct
23 Correct 49 ms 62656 KB Output is correct
24 Correct 85 ms 69932 KB Output is correct
25 Correct 64 ms 65600 KB Output is correct
26 Correct 532 ms 126908 KB Output is correct
27 Correct 596 ms 125524 KB Output is correct
28 Correct 620 ms 125840 KB Output is correct
29 Correct 676 ms 132636 KB Output is correct
30 Correct 870 ms 161496 KB Output is correct
31 Correct 1040 ms 175972 KB Output is correct
32 Correct 361 ms 216044 KB Output is correct
33 Correct 355 ms 207732 KB Output is correct
34 Correct 300 ms 80244 KB Output is correct
35 Correct 375 ms 88024 KB Output is correct
36 Correct 509 ms 97712 KB Output is correct
37 Correct 1062 ms 147624 KB Output is correct
38 Correct 1090 ms 148224 KB Output is correct
39 Correct 1132 ms 150908 KB Output is correct
40 Correct 1260 ms 159068 KB Output is correct
41 Correct 1595 ms 193784 KB Output is correct
42 Correct 1945 ms 237652 KB Output is correct
43 Correct 1101 ms 245664 KB Output is correct
44 Correct 1061 ms 235212 KB Output is correct
45 Correct 1408 ms 193632 KB Output is correct
46 Correct 31 ms 56684 KB Output is correct