Submission #732798

#	Time	Username	Problem	Language	Result	Execution time	Memory
732798		loctildore	Through Another Maze Darkly (CCO21_day1problem3)	C++14	25 / 25	1711 ms	450600 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
struct node {
    int l, r;
    node *lft, *rht;
    int tot;
    node(int tl, int tr): l(tl), r(tr), tot(0) {
        if (l + 1 == r) {
            lft = rht = NULL;
            return;
        }
        lft = new node(l, (l + r) / 2);
        rht = new node((l + r) / 2, r);
    }
    void add(int p) {
        if (p < l || p >= r) {
            return;
        }
        tot++;
        if (l + 1 == r) return;
        lft->add(p); rht->add(p);
    }
    int fnd(int x) {
        if (l + 1 == r) return l;
        if (lft->tot >= x) return lft->fnd(x);
        return rht->fnd(x - lft->tot);
    }
}* root;
int n, q;
int a, b, tb;
vector<int> grph[800069];
int lgc;
vector<int> lg[800069];
vector<pair<int,int>> vctr, qrys;
int ans[800069];
void dfs(int x, int rnd, int lst = -1) {
    vector<int> tmp[2];
    bool flag = false;
    for (auto i : grph[x]) {
        if (i == lst) {
            flag = true; continue;
        }
        tmp[flag].push_back(i);
    }
    for (auto i : tmp[1]) {
        vctr.push_back({i, rnd + 1});
        dfs(i, rnd + 1, x);
        vctr.push_back({x, rnd + 1});
    }
    for (auto i : tmp[0]) {
        vctr.push_back({i, rnd});
        dfs(i, rnd, x);
        vctr.push_back({x, rnd});
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin>>n>>q;
    for (int i = 0; i < n; i++) {
        cin>>a; cin>>tb; tb--;
        for (int j = 1; j < a; j++) {
            cin>>b; b--;
            grph[i].push_back(b);
        }
        grph[i].push_back(tb);
    }
    dfs(0, 0);
    root = new node(0, vctr.size());
    for (int i = 0; i < vctr.size(); i++) {
        vctr[i].f++;
        lg[vctr[i].s].push_back(i);
    }
    for (int i = 0; i < q; i++) {
        cin>>a;
        qrys.push_back({a, i});
    }
    sort(all(qrys));
    int cur = 0;
    for (auto tmp : qrys) {
        tie(a, b) = tmp;
        while (a - cur > root->tot && lgc < 800069) {
            cur += root->tot;
            for (auto i : lg[lgc]) {
                root->add(i);
            }
            lgc++;
        }
        a -= cur;
        a %= root->tot;
        if (!a) a = root->tot;
        ans[b] = vctr[root->fnd(a)].f;
    }
    for (int i = 0; i < q; i++) {
        cout<<ans[i]<<endl;
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:75:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 0; i < vctr.size(); i++) {
      |                     ~~^~~~~~~~~~~~~

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