//Do initial DFSs to naively find first results.
//When return to root after N runs, all lasers should point to parent.
#include <bits/stdc++.h>
#define int long long int
#define init(x, s) x = new std::remove_pointer<decltype(x)>::type[s]
std::vector<int> traversal;
std::vector<int> *connections;
int *walkTime;
int *parent;
int *laserIndex;
bool *seen;
int traverse(int node) {
walkTime[node] = 0;
for (auto sub: connections[node]) {
walkTime[node] += 2 + traverse(sub);
}
return walkTime[node];
}
int walk(int node, int steps) {
if (steps == 0) return node;
for (auto sub: connections[node]) {
if (walkTime[sub] + 2 == steps) return node;
if (walkTime[sub] + 2 <= steps) {
steps -= walkTime[sub] + 2;
} else {
return walk(sub, steps - 1);
}
}
assert(false);
}
signed main() {
int N, Q;
std::cin >> N >> Q;
init(connections, N);
init(walkTime, N);
init(parent, N);
init(laserIndex, N);
init(seen, N);
for (int i = 0; i < N; ++i) {
seen[i] = false;
laserIndex[i] = 0;
int k;
std::cin >> k;
for (int j = 0; j < k; ++j) {
int a;
std::cin >> a;
a--;
connections[i].push_back(a);
}
}
int current = 0;
int remaining = N;
while (current != 0 || remaining > 0) {
if (!seen[current]) {
seen[current] = true;
remaining--;
}
laserIndex[current] = (laserIndex[current] + 1) % connections[current].size();
traversal.push_back(current);
current = connections[current][laserIndex[current]];
}
#ifdef LOCAL
for (auto n: traversal) {
std::cout << n + 1 << " ";
}
std::cout << std::endl;
#endif
for (int i = 0; i < N; ++i) {
std::vector<int> subtrees;
int pIndex = laserIndex[i];
for (int j = pIndex + 1; j < connections[i].size(); ++j) {
subtrees.push_back(connections[i][j]);
}
for (int j = 0; j < pIndex; j++) {
subtrees.push_back(connections[i][j]);
}
if (i == 0) subtrees.push_back(connections[i][laserIndex[i]]);
connections[i] = subtrees;
}
traverse(0);
for (int i = 0; i < Q; ++i) {
int x;
std::cin >> x;
if (x < traversal.size()) {
std::cout << traversal[x] + 1 << std::endl;
} else {
x -= traversal.size();
x = x % walkTime[0];
std::cout << walk(0, x) + 1 << std::endl;
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:71:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int j = pIndex + 1; j < connections[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:84:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | if (x < traversal.size()) {
| ~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
997 ms |
526692 KB |
Output is correct |
3 |
Runtime error |
1446 ms |
1048576 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
352 KB |
Output is correct |
2 |
Correct |
4 ms |
468 KB |
Output is correct |
3 |
Correct |
12 ms |
4636 KB |
Output is correct |
4 |
Correct |
6 ms |
852 KB |
Output is correct |
5 |
Correct |
6 ms |
852 KB |
Output is correct |
6 |
Correct |
7 ms |
1104 KB |
Output is correct |
7 |
Correct |
7 ms |
1612 KB |
Output is correct |
8 |
Correct |
11 ms |
2632 KB |
Output is correct |
9 |
Correct |
25 ms |
8768 KB |
Output is correct |
10 |
Correct |
43 ms |
16940 KB |
Output is correct |
11 |
Correct |
48 ms |
17012 KB |
Output is correct |
12 |
Correct |
85 ms |
33332 KB |
Output is correct |
13 |
Correct |
40 ms |
16948 KB |
Output is correct |
14 |
Correct |
42 ms |
17008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
625 ms |
263892 KB |
Output is correct |
2 |
Runtime error |
3081 ms |
1048576 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
997 ms |
526692 KB |
Output is correct |
3 |
Runtime error |
1446 ms |
1048576 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |