Submission #1167421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167421		yoshi_33550336	Through Another Maze Darkly (CCO21_day1problem3)	C++20	4 / 25	9092 ms	203952 KiB

Main

#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_64 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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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