oj.uz

Submission #576332

# Submission time Handle Problem Language Result Execution time Memory
576332 2022-06-13T03:18:26 Z eecs Through Another Maze Darkly (CCO21_day1problem3) C++17
4 / 25
 4812 ms 1048576 KB 
#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;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19128 KB Output is correct
2 Correct 910 ms 282484 KB Output is correct
3 Runtime error 2391 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19156 KB Output is correct
2 Correct 13 ms 19284 KB Output is correct
3 Correct 23 ms 21296 KB Output is correct
4 Correct 15 ms 19512 KB Output is correct
5 Correct 27 ms 19444 KB Output is correct
6 Correct 29 ms 19596 KB Output is correct
7 Correct 17 ms 19892 KB Output is correct
8 Correct 24 ms 20308 KB Output is correct
9 Correct 33 ms 23420 KB Output is correct
10 Correct 50 ms 27648 KB Output is correct
11 Correct 54 ms 27532 KB Output is correct
12 Correct 76 ms 35744 KB Output is correct
13 Correct 46 ms 27548 KB Output is correct
14 Correct 44 ms 27540 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 151204 KB Output is correct
2 Runtime error 4812 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19128 KB Output is correct
2 Correct 910 ms 282484 KB Output is correct
3 Runtime error 2391 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -