Submission #635882

#	Time	Username	Problem	Language	Result	Execution time	Memory
635882		phathnv	Through Another Maze Darkly (CCO21_day1problem3)	C++11	25 / 25	1322 ms	319336 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 2e6 + 10;

int n, q, timer;
vector<int> adj[N];
vector<array<int, 2>> phase[N];

void dfs(int u, int p, int t) {
    phase[t].push_back({++timer, u});

    bool mark = false;
    for (int v : adj[u]) {
        if (v == p) {
            mark = true;
            continue;
        }
        if (mark) {
            dfs(v, u, t + 1);
            phase[t + 1].push_back({++timer, u});
        }
    }
    for (int v : adj[u]) {
        if (v == p) {
            break;
        }
        dfs(v, u, t);
        phase[t].push_back({++timer, u});
    }
}

struct SegTree {
    int n;
    vector<int> cnt, val;
    void init(int _n) {
        n = _n;
        cnt.assign(n * 4 + 1, 0);
        val.assign(n + 1, 0);
    }
    void setVal(int id, int l, int r, int pos, int x) {
        if (pos < l || r < pos) {
            return;
        }
        if (l == r) {
            assert(val[l] == 0);
            val[l] = x;
            cnt[id] = 1;
            return;
        }
        int mid = (l + r) >> 1;
        setVal(id << 1, l, mid, pos, x);
        setVal(id << 1 | 1, mid + 1, r, pos, x);
        cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
    }
    int getKth(int id, int l, int r, int k) {
        if (cnt[id] < k) {
            return 0;
        }
        if (l == r) {
            assert(k == 1 && val[l] != 0);
            return val[l];
        }
        int mid = (l + r) >> 1;
        int ans = getKth(id << 1, l, mid, k);
        if (ans == 0) {
            ans = getKth(id << 1 | 1, mid + 1, r, k - cnt[id << 1]);
        }
        assert(ans != 0);
        return ans;
    }

    void setVal(int pos, int val) {
        assert(1 <= pos && pos <= n && val > 0);
        setVal(1, 1, n, pos, val);
    }
    int getKth(int k) {
        assert(k >= 1);
        int ans = getKth(1, 1, n, k);
        assert(ans != 0);
        return ans;
    }
} ST;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k;
        adj[i].resize(k);
        for (auto &x : adj[i]) {
            cin >> x;
        }
        rotate(adj[i].begin(), adj[i].begin() + 1, adj[i].end());
    }

    dfs(1, -1, 0);

//    for (int i = 0; i < n; ++i) {
//        cerr << "phase " << i << endl;
//        for (auto [t, u] : phase[i]) {
//            cerr << t << ' ' << u << endl;
//        }
//    }

    vector<int> ans(q);
    vector<array<long long, 2>> queries(q);
    for (int i = 0; i < q; ++i) {
        cin >> queries[i][0];
        queries[i][1] = i;
    }
    sort(queries.begin(), queries.end());

    ST.init(timer);
    long long sum = 0;
    int cnt = 0, p = 0;
    for (auto [k, ind] : queries) {
        ++k;
        while (p < n) {
            if (sum + cnt < k) {
                sum += max(0, cnt - 1);
                for (auto [pos, val] : phase[p]) {
                    ST.setVal(pos, val);
                    ++cnt;
                }
                ++p;
            } else {
                k -= sum;
                ans[ind] = ST.getKth(k);
                break;
            }
        }
        if (!ans[ind]) {
            k -= sum;
            ans[ind] = ST.getKth((k - 1) % (cnt - 1) + 1);
        }
    }

    for (auto x : ans) {
        cout << x << '\n';
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:120:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |     for (auto [k, ind] : queries) {
      |               ^
Main.cpp:125:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |                 for (auto [pos, val] : phase[p]) {
      |                           ^

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