#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
const ll N = 1e6 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 450;
ll n,q,m = 0;
vector<ll>adj[N], row[N], g[N], pos[N];
vector<pll>t[N];
ll idx[N], ps[N], res[N];
vector<ll>topo;
void dfs(ll u, ll par){
m = max(m, idx[u]);
ll pos = -1;
for(int i = 0; i < adj[u].size();i++) if(adj[u][i] == par) pos = i;
for(int i = 0; i < adj[u].size();i++){
ll v = adj[u][i];
if(i < pos) idx[v] = idx[u];
else if(i > pos) idx[v] = idx[u] + 1;
}
for(auto v : adj[u]) if(v != par) dfs(v, u);
for(int i = pos + 1; i < adj[u].size();i++) g[u].pb(adj[u][i]);
for(int i = 0; i < pos;i++) g[u].pb(adj[u][i]);
}
void dfs_topo(ll u){
for(auto v : g[u]) {
topo.pb(v);
row[idx[v]].pb((ll)topo.size() - 1);
dfs_topo(v);
topo.pb(u);
row[idx[v]].pb((ll)topo.size() - 1);
}
}
struct fenwick_tree{
ll n;
vector<ll>ft;
void init(ll _n){
n = _n;
ft.resize(n + 10);
}
void update(ll idx, ll val){
while(idx <= n) ft[idx] = ft[idx] + val, idx += (idx & (-idx));
}
ll get(ll idx){
ll res = 0;
while(idx > 0) res = res + ft[idx], idx -= (idx & (-idx));
return res;
}
} ft;
void to_thic_cau(){
cin >> n >> q;
for(int i = 1; i <= n;i++){
ll k; cin >> k;
vector<ll>tmp;
for(int j = 1; j <= k;j++){
ll x; cin >> x;
tmp.pb(x);
}
for(int j = 1; j < tmp.size();j++) adj[i].pb(tmp[j]);
adj[i].pb(tmp[0]);
}
idx[1] = 1;
topo.pb(0);
dfs(1, 0);
dfs_topo(1);
ll tot = 0;
for(int i = 1; i <= m;i++){
tot += (ll)row[i].size();
ps[i] = ps[i-1] + tot;
}
for(int i = 1; i <= q;i++){
ll k; cin >> k;
ll j = lower_bound(ps + 1, ps + m + 1, k) - ps;
if(j > m){
res[i] = topo[(k - ps[m] - 1) % (ll)topo.size() + 1];
}
else t[j].pb({k - ps[j-1], i});
}
ft.init((ll)topo.size());
for(int i = 1; i <= m;i++){
for(auto x : row[i]) ft.update(x, 1);
for(auto x : t[i]){
ll val = x.F, idx = x.S;
ll l = 1, r = (ll)topo.size() - 1, pos = -1;
while(l <= r){
ll mid = (l + r) / 2;
if(ft.get(mid) >= val) pos = mid, r = mid - 1;
else l = mid + 1;
}
res[idx] = topo[pos];
}
}
for(int i = 1; i <= q;i++) cout << res[i] << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll tc = 1;
//cin >> tc;
while(tc--) to_thic_cau();
}
Compilation message
Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i = 0; i < adj[u].size();i++) if(adj[u][i] == par) pos = i;
| ~~^~~~~~~~~~~~~~~
Main.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int i = 0; i < adj[u].size();i++){
| ~~^~~~~~~~~~~~~~~
Main.cpp:30:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i = pos + 1; i < adj[u].size();i++) g[u].pb(adj[u][i]);
| ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void to_thic_cau()':
Main.cpp:67:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int j = 1; j < tmp.size();j++) adj[i].pb(tmp[j]);
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
21 ms |
120656 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
27 ms |
120740 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
122060 KB |
Output is correct |
2 |
Correct |
52 ms |
128288 KB |
Output is correct |
3 |
Correct |
85 ms |
138168 KB |
Output is correct |
4 |
Incorrect |
81 ms |
133056 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
21 ms |
120656 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |