Submission #1207124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207124		thangdzwinioi	Through Another Maze Darkly (CCO21_day1problem3)	C++20	25 / 25	800 ms	199788 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAX = 8e5 + 5;

int n, q;
vector <int> adj[MAX], sl[MAX];
int tot = 0, dfn[MAX << 1], level[MAX];

void dfs(int u, int fa){
    if (u > 1){
        dfn[++ tot] = u;
        sl[level[u]].push_back(tot);
    }

    int flag = 0;
    for (int v : adj[u]){
        if (flag){
            level[v] = level[u] + 1;
            dfs(v, u);
            dfn[++ tot] = u;
            sl[level[v]].push_back(tot);
        }
        if (v == fa) flag = 1;
    }

    for (int v : adj[u]){
        if (v == fa) break;
        level[v] = level[u];
        dfs(v, u);
        dfn[++ tot] = u;
        sl[level[v]].push_back(tot);
    }
}

int bit[MAX << 1];

void update(int p){
    for (; p <= tot; p += p & -p)
        bit[p] ++;
}

int get(int p = tot){
    int ans = 0;
    for (; p; p -= p & -p)
        ans += bit[p];
    return ans;
}

int lw(int k){
    int p = 0, sum = 0;
    for (int l = 20; l >= 0; -- l){
        int np = p + (1 << l);
        if (np <= tot && sum + bit[np] < k){
            p = np;
            sum += bit[np];
        }
    }
    return p + 1;
}

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

    level[1] = 1;
    dfs(1, 0);

    vector <pair <ll, int>> queries(q);
    for (int i = 0; i < q; ++ i){
        cin >> queries[i].first;
        queries[i].second = i;
    }
    sort(queries.begin(), queries.end());

    vector <int> ans(q);
    ll cur = 0;
    int j = 1;

    for (auto [k, id] : queries){
        for (; j <= n && cur < k; ++ j){
            for (int p : sl[j]) update(p);
            cur += get();
        }

        ll x = k - (cur - get());
        if (j > n) ans[id] = dfn[(x - 1) % tot + 1];
        else ans[id] = dfn[lw(x)];
    }

    for (int u : ans)
        cout << u << "\n";
}

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

    process();
    return 0;
}

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