Submission #1157659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157659		lto5	Through Another Maze Darkly (CCO21_day1problem3)	C++20	4 / 25	9097 ms	685272 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using M = array<int64_t, 3>;

const array<int64_t, 3> mods = {192982099304786663, 732609036414460277, 366366846147574687};

M operator*(const M& m1, const M& m2) {
  return M{(int64_t)(__int128_t(m1[0]) * m2[0] % mods[0]),
           int64_t(__int128_t(m1[1]) * m2[1] % mods[1]),
           int64_t(__int128_t(m1[2]) * m2[2] % mods[2])};
}

M operator*(const M& m1, const int& x) {
  return M{int64_t(__int128_t(m1[0]) * x % mods[0]),
           int64_t(__int128_t(m1[1]) * x % mods[1]),
           int64_t(__int128_t(m1[2]) * x % mods[2])};
}

M operator+(const M& m1, const M& m2) {
  M m = m1;
  for (int j = 0; j < 3; j++) {
    m[j] += m2[j];
    if (m[j] >= mods[j]) m[j] -= mods[j];
  }
  return m;
}

M operator+(const M& m1, const int& x) {
  M m = m1;
  for (int j = 0; j < 3; j++) {
    m[j] += x;
    if (m[j] >= mods[j]) m[j] -= mods[j];
  }
  return m;
}

M operator-(const M& m1, const M& m2) {
  M m = m1;
  for (int j = 0; j < 3; j++) {
    m[j] -= m2[j];
    if (m[j] < 0) m[j] += mods[j];
  }
  return m;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL
#define task "a"
#else
#define task "MAZE"
#endif
  if (fopen(task ".inp", "r")) {
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  int n, q;
  cin >> n >> q;
  vector<vector<int>> adj(n + 1);
  for (int i = 1; i <= n; i++) {
    int sz;
    cin >> sz;
    adj[i].resize(sz);
    for (auto& it : adj[i]) cin >> it;
  }
  vector<int> ptr(n + 1);
  const int BASE = 9057571;
  M H = {0, 0, 0};
  vector<M> power(n + 1);
  power[0] = {1, 1, 1};
  for (int i = 1; i <= n; i++) {
    power[i] = power[i - 1] * BASE;
    H = H * BASE + (ptr[i] + 1);
  }
  vector<int> smal = {0};
  int curr = 1;
  map<pair<M, int>, int> mpp;
  int sta = -1, len = -1;
  for (int i = 1;; i++) {
    if (mpp.count({H, curr})) {
      sta = mpp[{H, curr}];
      len = i - mpp[{H, curr}];
      break;
    }
    mpp[{H, curr}] = i;
    H = H - power[n - curr] * (ptr[curr] + 1);
    ++ptr[curr];
    if (ptr[curr] >= int(adj[curr].size())) ptr[curr] = 0;
    H = H + power[n - curr] * (ptr[curr] + 1);
    curr = adj[curr][ptr[curr]];
    smal.push_back(curr);
  }
  assert(sta != -1);
  while (q--) {
    int64_t k;
    cin >> k;
    if (k <= sta)
      cout << smal[k] << "\n";
    else {
      int64_t buoc = (k - sta) % len;
      cout << smal[sta + buoc] << "\n";
    }
  }
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:58:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     freopen(task ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 4 / 4
• Subtask 3: 0 / 12
• Subtask 4: 0 / 5