oj.uz

Submission #576650

# Submission time Handle Problem Language Result Execution time Memory
576650 2022-06-13T08:55:12 Z eecs Through Another Maze Darkly (CCO21_day1problem3) C++17
4 / 25
 657 ms 173632 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 800010;
int n, m, tot, ver[maxn], lev[maxn], id[maxn], ans[maxn];
ll q[maxn];
vector<int> G[maxn], V[maxn];

#define mid ((l + r) >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
int sz[maxn << 3];

void upd(int k, int l, int r, int p) {
    sz[k]++;
    if (l < r) mid >= p ? upd(ls, l, mid, p) : upd(rs, mid + 1, r, p);
}

int get(int k, int l, int r, int p) {
    if (l == r) return ver[l];
    return sz[ls] >= p ? get(ls, l, mid, p) : get(rs, mid + 1, r, p - sz[ls]);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 1, k; i <= n; i++) {
        cin >> k, G[i].resize(k);
        for (int &x : G[i]) cin >> x;
        rotate(G[i].begin(), G[i].begin() + 1, G[i].end());
    }
    auto dfs = [&](auto self, int u, int fa) -> void {
        if (u > 1) ver[++tot] = u, V[lev[u]].push_back(tot);
        bool flag = 0;
        for (int v : G[u]) {
            if (v == fa) { flag = 1; continue; }
            if (!flag) continue;
            lev[v] = lev[u] + 1, self(self, v, u);
            ver[++tot] = u, V[lev[v]].push_back(tot);
        }
        for (int v : G[u]) {
            if (v == fa) break;
            lev[v] = lev[u], self(self, v, u);
            ver[++tot] = u, V[lev[v]].push_back(tot);
        }
    };
    lev[1] = 1, dfs(dfs, 1, 0);
    for (int i = 1; i <= m; i++) {
        cin >> q[i];
    }
    iota(id + 1, id + m + 1, 1);
    sort(id + 1, id + m + 1, [&](int i, int j) { return q[i] < q[j]; });
    long long cur = 0;
    for (int i = 1, j = 1; i <= m; i++) {
        for (; j <= n && cur < q[id[i]]; j++) {
            for (int x : V[j]) upd(1, 1, tot, x);
            cur += sz[1];
        }
        long long x = q[id[i]] - (cur - sz[1]);
        ans[id[i]] = get(1, 1, tot, (x - 1) % (2 * n - 2) + 1);
    }
    for (int i = 1; i <= m; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37844 KB Output is correct
2 Correct 31 ms 39948 KB Output is correct
3 Correct 109 ms 58776 KB Output is correct
4 Incorrect 657 ms 173632 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37972 KB Output is correct
2 Correct 22 ms 38020 KB Output is correct
3 Correct 21 ms 38044 KB Output is correct
4 Correct 24 ms 38128 KB Output is correct
5 Correct 26 ms 38108 KB Output is correct
6 Correct 26 ms 38044 KB Output is correct
7 Correct 24 ms 38100 KB Output is correct
8 Correct 20 ms 38044 KB Output is correct
9 Correct 19 ms 38184 KB Output is correct
10 Correct 19 ms 38220 KB Output is correct
11 Correct 21 ms 38224 KB Output is correct
12 Correct 21 ms 38228 KB Output is correct
13 Correct 20 ms 38228 KB Output is correct
14 Correct 19 ms 38228 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 38904 KB Output is correct
2 Correct 42 ms 43016 KB Output is correct
3 Correct 72 ms 49820 KB Output is correct
4 Correct 72 ms 47308 KB Output is correct
5 Incorrect 422 ms 96212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37844 KB Output is correct
2 Correct 31 ms 39948 KB Output is correct
3 Correct 109 ms 58776 KB Output is correct
4 Incorrect 657 ms 173632 KB Output isn't correct
5 Halted 0 ms 0 KB -