oj.uz

Submission #576334

# Submission time Handle Problem Language Result Execution time Memory
576334 2022-06-13T03:22:52 Z eecs Through Another Maze Darkly (CCO21_day1problem3) C++17
4 / 25
 5437 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 800010;
int n, q, ptr[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> tmp;
    ll step = 0;
    for (int u = 1, cnt = 0; cnt < n || u > 1; step++) {
        if (!vis[u]) vis[u] = 1, cnt++;
        tmp.push_back(u = G[u][++ptr[u] %= G[u].size()]);
    }
    int u = 1;
    vector<int> res;
    for (int i = 0; i < 2 * n - 2; i++) {
        res.push_back(u), u = G[u][++ptr[u] %= G[u].size()];
    }
    while (q--) {
        ll k;
        cin >> k;
        if (k < step) cout << tmp[k - 1] << "\n";
        else cout << res[(k - step) % (2 * n - 2)] << "\n";
    }
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 875 ms 282728 KB Output is correct
3 Runtime error 2539 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 19164 KB Output is correct
2 Correct 12 ms 19276 KB Output is correct
3 Correct 24 ms 21404 KB Output is correct
4 Correct 14 ms 19512 KB Output is correct
5 Correct 13 ms 19440 KB Output is correct
6 Correct 13 ms 19644 KB Output is correct
7 Correct 14 ms 19792 KB Output is correct
8 Correct 16 ms 20320 KB Output is correct
9 Correct 29 ms 23424 KB Output is correct
10 Correct 47 ms 27516 KB Output is correct
11 Correct 46 ms 27548 KB Output is correct
12 Correct 80 ms 35776 KB Output is correct
13 Correct 44 ms 27544 KB Output is correct
14 Correct 49 ms 27568 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 151128 KB Output is correct
2 Runtime error 5437 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 19028 KB Output is correct
2 Correct 875 ms 282728 KB Output is correct
3 Runtime error 2539 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -