제출 #576332

#제출 시각아이디문제언어결과실행 시간메모리
576332eecsThrough Another Maze Darkly (CCO21_day1problem3)C++17
4 / 25
4812 ms1048576 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 800010; int n, q, ptr[maxn], pos[maxn], fa[maxn]; bool vis[maxn]; vector<int> G[maxn]; int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> q; for (int i = 1, k; i <= n; i++) { cin >> k; while (k--) { int c; cin >> c, G[i].push_back(c); } } auto dfs = [&](auto self, int u) -> void { for (int v : G[u]) if (v ^ fa[u]) { fa[v] = u, self(self, v); } }; dfs(dfs, 1); vector<int> res; ll step = 0; for (int x = 1, cnt = 0; cnt < n || x > 1; step++) { if (!vis[x]) vis[x] = 1, cnt++; res.push_back(x = G[x][++pos[x] %= G[x].size()]); } while (q--) { ll k; cin >> k; if (k < step) { cout << res[k - 1] << "\n"; continue; } k = (k - step) % (2 * n - 2); copy(pos + 1, pos + n + 1, ptr + 1); int u = 1; while (k--) u = G[u][++ptr[u] %= G[u].size()]; cout << u << "\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...