제출 #576653

#제출 시각아이디문제언어결과실행 시간메모리
576653eecsThrough Another Maze Darkly (CCO21_day1problem3)C++17
25 / 25
1239 ms216892 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 800010; int n, m, tot, ver[maxn << 1], lev[maxn], id[maxn], ans[maxn]; ll q[maxn]; vector<int> G[maxn], V[maxn]; #define mid ((l + r) >> 1) #define ls (k << 1) #define rs (k << 1 | 1) int sz[maxn << 3]; void upd(int k, int l, int r, int p) { sz[k]++; if (l < r) mid >= p ? upd(ls, l, mid, p) : upd(rs, mid + 1, r, p); } int get(int k, int l, int r, int p) { if (l == r) return ver[l]; return sz[ls] >= p ? get(ls, l, mid, p) : get(rs, mid + 1, r, p - sz[ls]); } int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> m; for (int i = 1, k; i <= n; i++) { cin >> k, G[i].resize(k); for (int &x : G[i]) cin >> x; rotate(G[i].begin(), G[i].begin() + 1, G[i].end()); } auto dfs = [&](auto self, int u, int fa) -> void { if (u > 1) ver[++tot] = u, V[lev[u]].push_back(tot); bool flag = 0; for (int v : G[u]) { if (v == fa) { flag = 1; continue; } if (!flag) continue; lev[v] = lev[u] + 1, self(self, v, u); ver[++tot] = u, V[lev[v]].push_back(tot); } for (int v : G[u]) { if (v == fa) break; lev[v] = lev[u], self(self, v, u); ver[++tot] = u, V[lev[v]].push_back(tot); } }; lev[1] = 1, dfs(dfs, 1, 0); for (int i = 1; i <= m; i++) { cin >> q[i]; } iota(id + 1, id + m + 1, 1); sort(id + 1, id + m + 1, [&](int i, int j) { return q[i] < q[j]; }); long long cur = 0; for (int i = 1, j = 1; i <= m; i++) { for (; j <= n && cur < q[id[i]]; j++) { for (int x : V[j]) upd(1, 1, tot, x); cur += sz[1]; } long long x = q[id[i]] - (cur - sz[1]); ans[id[i]] = get(1, 1, tot, (x - 1) % (2 * n - 2) + 1); } for (int i = 1; i <= m; i++) { cout << ans[i] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...