#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int SZ = 1 << 21;
int N, Q, S[808080], On[808080], R[808080], T[SZ];
vector<int> G[80808];
vector<pair<int,int>> Tour;
vector<int> Idx[808080]; // Idx[t] : t에 켜지는 정점
ll TourSize[808080];
void Add(int x, int v){ for(x+=3; x<SZ; x+=x&-x) T[x] += v; }
int Get(int x){ int ret = 0; for(x+=3; x; x-=x&-x) ret += T[x]; return ret; }
int Kth(int x){
int l = 0, r = Tour.size() - 1;
while(l < r){
int m = (l + r) / 2;
if(Get(m) >= x) r = m;
else l = m + 1;
}
return r;
}
void GetFirstEdge(int v, int b=-1){
int st = G[v][0];
int pa = find(G[v].begin(), G[v].end(), b) - G[v].begin();
if(pa != G[v].size()){
int idx = (pa + 1) % G[v].size();
rotate(G[v].begin(), G[v].begin()+idx, G[v].end());
S[v] = find(G[v].begin(), G[v].end(), st) - G[v].begin();
}
for(auto i : G[v]) if(i != b) GetFirstEdge(i, v);
}
void GetTime(int v, int b=-1, int t=1){
On[v] = t;
for(int i=0; i<G[v].size(); i++) if(G[v][i] != b) GetTime(G[v][i], v, t + (i < S[v]));
}
inline void AddEdge(int s, int e){
Idx[max(On[s], On[e])].push_back(Tour.size());
Tour.emplace_back(s, e);
}
void GetTour(int v, int b=-1){
for(auto i : G[v]) if(i != b) AddEdge(v, i), GetTour(i, v), AddEdge(i, v);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> N >> Q;
for(int i=1; i<=N; i++){
int sz; cin >> sz; G[i].resize(sz);
for(auto &j : G[i]) cin >> j;
rotate(G[i].begin(), G[i].begin()+1, G[i].end());
}
GetFirstEdge(1);
GetTime(1);
GetTour(1);
for(int i=1; i<=N; i++) TourSize[i] = TourSize[i-1] + Idx[i].size();
for(int i=1; i<=N; i++) TourSize[i] += TourSize[i-1];
vector<tuple<ll,ll,ll>> V; // iteration, kth, idx
for(int q=1; q<=Q; q++){
ll K; cin >> K;
int it = lower_bound(TourSize+1, TourSize+N+1, K) - TourSize;
K -= TourSize[it-1];
if(it == N+1) K = (K - 1) % TourSize[N] + 1;
V.emplace_back(it, K, q);
}
sort(V.begin(), V.end());
for(int it=1, i=0; it<=N+1; it++){
for(auto e : Idx[it]) Add(e, 1);
while(i < V.size() && get<0>(V[i]) == it){
R[get<2>(V[i])] = Kth(get<1>(V[i]));
i += 1;
}
}
for(int i=1; i<=Q; i++) cout << Tour[R[i]].second << "\n";
}
Compilation message
Main.cpp: In function 'void GetFirstEdge(int, int)':
Main.cpp:27:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | if(pa != G[v].size()){
| ~~~^~~~~~~~~~~~~~
Main.cpp: In function 'void GetTime(int, int, int)':
Main.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i=0; i<G[v].size(); i++) if(G[v][i] != b) GetTime(G[v][i], v, t + (i < S[v]));
| ~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | while(i < V.size() && get<0>(V[i]) == it){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
21204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
21332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
22528 KB |
Output is correct |
| 2 |
Correct |
42 ms |
28372 KB |
Output is correct |
| 3 |
Incorrect |
98 ms |
37264 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
21204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
