#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int maxn = 800005;
struct Node{
int ls, rs;
int cnt;
}tr[(maxn * 2) * (4 + 20)];
int root[maxn << 1], idx;
vector<int> to[maxn], pos[maxn], ne;
int n, Q, m;
int seq[maxn << 1], len;
int fa[maxn], ind[maxn];
int now[maxn], tot;
ll sum[maxn];
queue<int> q;
int build(int l, int r){
int p = ++ idx;
if (l == r){
return p;
}
tr[p].ls = build(l, mid), tr[p].rs = build(mid + 1, r);
return p;
}
int insert(int p, int l, int r, int x){
int q = ++ idx;
tr[q] = tr[p];
if (l == r){
tr[q].cnt = 1;
return q;
}
if (x <= mid) tr[q].ls = insert(tr[p].ls, l, mid, x);
else tr[q].rs = insert(tr[p].rs, mid + 1, r, x);
tr[q].cnt = tr[tr[q].ls].cnt + tr[tr[q].rs].cnt;
return q;
}
int query(int p, int l, int r, int k){//Kth problem
if (l == r){
return l;
}
int cnt = tr[tr[p].ls].cnt;
if (cnt >= k) return query(tr[p].ls, l, mid, k);
else return query(tr[p].rs, mid + 1, r, k - cnt);
}
void init(int u, int _fa){
fa[u] = _fa;
for (int i = 0; i < to[u].size(); i ++){
int v = to[u][i];
if (v == fa[u]){
ind[u] = i;
continue;
}
init(v, u);
}
}
void get(int u){
if (u > 1) seq[++ len] = u, pos[u].push_back(len);
int i = ind[u];
while (true){
i ++, i %= to[u].size();
int v = to[u][i];
if (i == ind[u] && u > 1) break;
get(v);
seq[++ len] = u, pos[u].push_back(len);
if (i == ind[u] && u == 1) break;
}
}
void dfs(int u, int t){
now[u] ++, now[u] %= to[u].size();
if (u != t){
root[m] = insert(root[m], 1, len, *pos[u].rbegin());
pos[u].pop_back();
}
if (now[u] == ind[u] && u != t){
ne.push_back(u);
return;
}
int i = now[u] - 1;
int back_up = now[u];
while (true){
i ++, i %= to[u].size(), now[u] = i;
int v = to[u][i];
if (i == ind[u] && u > 1) break;
dfs(v, t);
root[m] = insert(root[m], 1, len, *pos[u].rbegin());
pos[u].pop_back();
if (i == ind[u] && u == 1) break;
}
ind[u] = back_up;
if (!pos[u].empty()) ne.push_back(u);
return;
}
void file(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#define task "MAZE"
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
}
int32_t main() {
file();
cin >> n >> Q;
for (int u = 1, k, v; u <= n; u ++){
cin >> k;
while (k --){
cin >> v;
to[u].push_back(v);
}
}
init(1, 0), get(1);
q.push(1), root[0] = build(1, len);
while (!q.empty()){
m ++, root[m] = root[m - 1];
while (!q.empty()){
int u = q.front();
q.pop();
dfs(u, u);
}
for (vector<int>::iterator it = ne.begin(); it != ne.end(); it ++){
q.push(*it);
}
ne.clear();
sum[m] = sum[m - 1] + tr[root[m]].cnt;
if (tr[root[m]].cnt == len) break;
}
ll k;
while (Q --){
cin >> k;
int t = lower_bound(sum + 1, sum + m + 1, k) - sum;
k -= sum[t - 1];
if (t < m){
cout << seq[query(root[t], 1, len, k)] << endl;
}
else{
k %= len;
if (k == 0) k = len;
cout << seq[k] << endl;
}
}
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'void file()':
Main.cpp:110:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:111:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |