#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>
#define int ll
using namespace std;
typedef long long ll;
vector<int> adj[800002];
vector<vector<int>> levNode;
vector<pair<int, int>> path;
vector<pair<ll, int>> ask;
int ans[800002];
int T[6400000];
void upd(int i, int l, int r, int id)
{
if(l == r)
{
T[i]++;
return;
}
int m = (l + r)/2;
if(id <= m) upd(i*2, l, m, id);
else upd(i*2+1, m+1, r, id);
T[i] = T[i*2] + T[i*2+1];
}
int f(int i, int l, int r, int id)
{
if(l == r) return path[l].first;
int m = (l + r)/2;
if(T[i*2] < id) return f(i*2+1, m+1, r, id-T[i*2]);
else return f(i*2, l, m, id);
}
int maxLev = 0;
void dfs(int x, int p, int lev)
{
maxLev = max(maxLev, lev);
if(x != 1) path.push_back({x, lev});
int sz = (int)adj[x].size();
int loc = 0;
if(x == 1)
{
for(int i=1;i<sz;i++)
{
dfs(adj[x][i], x, lev);
path.push_back({x, lev});
}
dfs(adj[x][0], x, lev);
path.push_back({x, lev});
return;
}
for(int i=0;i<sz;i++)
{
if(adj[x][i] == p)
{
loc = i;
break;
}
}
if(loc == 0)
{
for(int i=1;i<sz;i++) {
dfs(adj[x][i], x, lev);
path.push_back({x, lev});
}
}
else
{
for(int i=loc+1;i<sz;i++) {
dfs(adj[x][i], x, lev+1);
path.push_back({x, lev+1});
}
dfs(adj[x][0], x, lev+1);
path.push_back({x, lev+1});
for(int i=1;i<loc;i++) {
dfs(adj[x][i], x, lev);
path.push_back({x, lev});
}
}
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(NULL);
int n, q; cin >> n >> q;
for(int i=1;i<=n;i++)
{
int c; cin >> c;
for(int j=1;j<=c;j++)
{
int v; cin >> v;
adj[i].push_back(v);
}
}
dfs(1, -1, 0);
int L = (int)path.size();
levNode.resize(maxLev+1);
for(int i=0;i<L;i++)
{
//cout << path[i].first << " " << path[i].second << "\n";
levNode[path[i].second].push_back(i);
}
for(int i=1;i<=q;i++)
{
ll asdf; cin >> asdf;
ask.push_back({asdf, i});
}
sort(ask.begin(), ask.end());
ll now = 0, num = 0, nL = 0;
for(int i=0;i<q;i++)
{
while(now < ask[i].first && nL <= maxLev)
{
num += levNode[nL].size();
now += num;
for(int j : levNode[nL]){
upd(1, 0, L-1, j);
}
nL++;
}
if(nL <= maxLev)
{
ll x = ask[i].first - now + num;
ans[ask[i].second] = f(1, 0, L-1, x);
}
else
{
ll x = (ask[i].first - now + L)%L;
if(x == 0) x = L;
ans[ask[i].second] = f(1, 0, L-1, x);
}
}
for(int i=1;i<=q;i++)
{
cout << ans[i] << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19044 KB |
Output is correct |
2 |
Correct |
19 ms |
22220 KB |
Output is correct |
3 |
Correct |
120 ms |
49332 KB |
Output is correct |
4 |
Correct |
790 ms |
242960 KB |
Output is correct |
5 |
Correct |
1089 ms |
274184 KB |
Output is correct |
6 |
Correct |
1055 ms |
262112 KB |
Output is correct |
7 |
Correct |
292 ms |
62484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19156 KB |
Output is correct |
2 |
Correct |
10 ms |
19156 KB |
Output is correct |
3 |
Correct |
10 ms |
19284 KB |
Output is correct |
4 |
Correct |
11 ms |
19380 KB |
Output is correct |
5 |
Correct |
14 ms |
19416 KB |
Output is correct |
6 |
Correct |
12 ms |
19412 KB |
Output is correct |
7 |
Correct |
12 ms |
19412 KB |
Output is correct |
8 |
Correct |
12 ms |
19412 KB |
Output is correct |
9 |
Correct |
11 ms |
19540 KB |
Output is correct |
10 |
Correct |
13 ms |
19604 KB |
Output is correct |
11 |
Correct |
11 ms |
19540 KB |
Output is correct |
12 |
Correct |
11 ms |
19676 KB |
Output is correct |
13 |
Correct |
11 ms |
19668 KB |
Output is correct |
14 |
Correct |
11 ms |
19508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
20588 KB |
Output is correct |
2 |
Correct |
33 ms |
26028 KB |
Output is correct |
3 |
Correct |
83 ms |
36948 KB |
Output is correct |
4 |
Correct |
81 ms |
34408 KB |
Output is correct |
5 |
Correct |
436 ms |
129748 KB |
Output is correct |
6 |
Correct |
459 ms |
130440 KB |
Output is correct |
7 |
Correct |
452 ms |
109044 KB |
Output is correct |
8 |
Correct |
479 ms |
117512 KB |
Output is correct |
9 |
Correct |
549 ms |
152788 KB |
Output is correct |
10 |
Correct |
560 ms |
167304 KB |
Output is correct |
11 |
Correct |
514 ms |
236268 KB |
Output is correct |
12 |
Correct |
451 ms |
209252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19044 KB |
Output is correct |
2 |
Correct |
19 ms |
22220 KB |
Output is correct |
3 |
Correct |
120 ms |
49332 KB |
Output is correct |
4 |
Correct |
790 ms |
242960 KB |
Output is correct |
5 |
Correct |
1089 ms |
274184 KB |
Output is correct |
6 |
Correct |
1055 ms |
262112 KB |
Output is correct |
7 |
Correct |
292 ms |
62484 KB |
Output is correct |
8 |
Correct |
10 ms |
19156 KB |
Output is correct |
9 |
Correct |
10 ms |
19156 KB |
Output is correct |
10 |
Correct |
10 ms |
19284 KB |
Output is correct |
11 |
Correct |
11 ms |
19380 KB |
Output is correct |
12 |
Correct |
14 ms |
19416 KB |
Output is correct |
13 |
Correct |
12 ms |
19412 KB |
Output is correct |
14 |
Correct |
12 ms |
19412 KB |
Output is correct |
15 |
Correct |
12 ms |
19412 KB |
Output is correct |
16 |
Correct |
11 ms |
19540 KB |
Output is correct |
17 |
Correct |
13 ms |
19604 KB |
Output is correct |
18 |
Correct |
11 ms |
19540 KB |
Output is correct |
19 |
Correct |
11 ms |
19676 KB |
Output is correct |
20 |
Correct |
11 ms |
19668 KB |
Output is correct |
21 |
Correct |
11 ms |
19508 KB |
Output is correct |
22 |
Correct |
15 ms |
20588 KB |
Output is correct |
23 |
Correct |
33 ms |
26028 KB |
Output is correct |
24 |
Correct |
83 ms |
36948 KB |
Output is correct |
25 |
Correct |
81 ms |
34408 KB |
Output is correct |
26 |
Correct |
436 ms |
129748 KB |
Output is correct |
27 |
Correct |
459 ms |
130440 KB |
Output is correct |
28 |
Correct |
452 ms |
109044 KB |
Output is correct |
29 |
Correct |
479 ms |
117512 KB |
Output is correct |
30 |
Correct |
549 ms |
152788 KB |
Output is correct |
31 |
Correct |
560 ms |
167304 KB |
Output is correct |
32 |
Correct |
514 ms |
236268 KB |
Output is correct |
33 |
Correct |
451 ms |
209252 KB |
Output is correct |
34 |
Correct |
272 ms |
50276 KB |
Output is correct |
35 |
Correct |
326 ms |
59836 KB |
Output is correct |
36 |
Correct |
418 ms |
72816 KB |
Output is correct |
37 |
Correct |
962 ms |
183056 KB |
Output is correct |
38 |
Correct |
979 ms |
182616 KB |
Output is correct |
39 |
Correct |
1074 ms |
184660 KB |
Output is correct |
40 |
Correct |
1113 ms |
194168 KB |
Output is correct |
41 |
Correct |
1272 ms |
235096 KB |
Output is correct |
42 |
Correct |
1198 ms |
284428 KB |
Output is correct |
43 |
Correct |
953 ms |
295504 KB |
Output is correct |
44 |
Correct |
997 ms |
283452 KB |
Output is correct |
45 |
Correct |
804 ms |
202080 KB |
Output is correct |
46 |
Correct |
10 ms |
19020 KB |
Output is correct |