Submission #1199033

#TimeUsernameProblemLanguageResultExecution timeMemory
1199033caccaccacThrough Another Maze Darkly (CCO21_day1problem3)C++20
4 / 25
9091 ms203884 KiB
#include <bits/stdc++.h> using namespace std; #ifndef yoshi_likes_e4 #define endl '\n' #endif #define problem "MAZE" #define multitest 0 #define debug(x) cerr << #x << " = " << x << endl; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<vector<int>> rd; void init() { } struct gxh { int n; vector<int> id; vector<vector<int>> R; uint64_t xh = 0; int v = 0; gxh(int n, vector<int> &id, vector<vector<int>> &R) : n(n), id(id), R(R) { for (int i = 0; i < n; i++) xh ^= rd[i][id[i]]; } void next() { xh ^= rd[v][id[v]]; id[v]++, id[v] %= R[v].size(); xh ^= rd[v][id[v]]; v = R[v][id[v]]; } pair<int, uint64_t> state() { return {v, xh}; } }; pair<int, int> floyd(int n, vector<int> &id, vector<vector<int>> &R) { gxh tortoise(n, id, R), hare(n, id, R); tortoise.next(); hare.next(); hare.next(); while (tortoise.state() != hare.state()) { tortoise.next(); hare.next(); hare.next(); } int mu = 0; tortoise = gxh(n, id, R); while (tortoise.state() != hare.state()) { tortoise.next(); hare.next(); mu++; } int lam = 1; hare = tortoise; hare.next(); while (tortoise.state() != hare.state()) { hare.next(); lam++; } return {mu, lam}; } void Yoshi() { int n, q; cin >> n >> q; vector<int> id(n); vector<vector<int>> R(n); rd.resize(n); for (int i = 0; i < n; i++) { int s; cin >> s; R[i].resize(s); rd[i].resize(s); for (int j = 0; j < s; j++) cin >> R[i][j], R[i][j]--, rd[i][j] = rng(); } int v = 0; auto f = floyd(n, id, R); vector<int> Qu(f.first + f.second); for (int i = 0; i < f.first + f.second; i++) { Qu[i] = v; id[v]++, id[v] %= R[v].size(); v = R[v][id[v]]; } while (q--) { uint64_t k; cin >> k; if (k >= f.first) cout << Qu[(k - f.first) % f.second + f.first] + 1 << endl; else cout << Qu[k] + 1 << endl; } } signed main() { #ifndef yoshi_likes_e4 ios::sync_with_stdio(0); cin.tie(0); if (fopen(problem ".inp", "r")) { freopen(problem ".inp", "r", stdin); freopen(problem ".out", "w", stdout); } #endif init(); int t = 1; #if multitest cin >> t; #endif while (t--) Yoshi(); }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen(problem ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(problem ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...