Submission #1102599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102599		CDuong	Through Another Maze Darkly (CCO21_day1problem3)	C++17	25 / 25	3169 ms	380364 KiB

Main

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
// #define int long long
#define isz(x) (int)x.size()
using namespace std;

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

void solve() {
    int n, q;
    cin >> n >> q;

    vector<vector<int>> g(n);
    for (int i = 0; i < n; ++i) {
        int cnt;
        cin >> cnt;

        g[i].resize(cnt);
        cin >> g[i].back();
        --g[i].back();
        for (int j = 0; j < cnt - 1; ++j) {
            cin >> g[i][j];
            --g[i][j];
        }

        // for (auto val : g[i]) {
        //     cout << val << " \n"[val == g[i].back()];
        // }
    }

    vector<int> d(n);
    vector<int> par(n, -1), bf(n), ptr(n);
    auto dfs = [&](auto self, int u) -> void {
        int cur = 0;
        for (auto v : g[u]) {
            bf[u] += 1 - cur;
            if (v == par[u]) {
                ++cur;
            }
            else {
                par[v] = u;
                d[v] = d[u] + cur;
                self(self, v);
            }
        }
    };
    dfs(dfs, 0);

    int tdfs = 0;
    ordered_set os;
    vector<vector<int>> av(n);
    vector<vector<int>> oth(n);
    vector<int> optr(n), tin(n), ord;
    auto dfs2 = [&](auto self, int u) -> void {
        av[d[u]].emplace_back(u);
        if (d[u] == 0) {
            os.insert(tdfs);
        }
        ord.emplace_back(u);
        tin[u] = tdfs++;

        int ptr = -1;
        for (int i = 0; i < isz(g[u]); ++i) {
            auto v = g[u][i];
            if (v == par[u]) {
                ptr = i;
                break;
            }
        }
        for (int i = ptr + 1; i < isz(g[u]); ++i) {
            auto v = g[u][i];
            self(self, v);
            if (d[u] == 0 and d[v] == 0) {
                os.insert(tdfs);
            }
            else {
                oth[u].emplace_back(tdfs);
            }
            ord.emplace_back(u);
            tdfs++;
        }
        for (int i = 0; i < ptr; ++i) {
            auto v = g[u][i];
            self(self, v);
            if (d[u] == 0 and d[v] == 0) {
                os.insert(tdfs);
            }
            else {
                oth[u].emplace_back(tdfs);
            }
            ord.emplace_back(u);
            tdfs++;
        }
    };
    dfs2(dfs2, 0);
    os.erase(os.find(--tdfs));

    for (int i = 0; i < n; ++i) {
        reverse(all(oth[i]));
    }

    // for (auto val : ord) {
    //     cout << val << " ";
    // }
    // cout << endl;

    int mx = *max_element(all(d));

    // ofstream out("bai3.out");
    // ofstream ans("bai3.ans");

    // int u = 0, cnt = 0, cook = 0;
    // out << u << " ";
    // while (true) {
    //     int v = g[u][ptr[u]];
    //     ptr[u] = (ptr[u] + 1) % isz(g[u]);
    //     if (v == 0 and ptr[v] == 0) {
    //         out << endl << cook << "\n";
    //         if (++cnt == mx + 1) {
    //             break;
    //         }
    //         cook = 0;
    //     }
    //     ++cook;
    //     out << (u = v) << " ";
    // }

    // for (int i = 0; i <= 10; ++i) {
    //     int step = 0;
    //     for (int u = 0; u < n; ++u) if (d[u] <= i) {
    //         step += (d[u] == i ? bf[u] : isz(g[u]));
    //     }
    //     cout << i << " " << step << endl;
    // }

    vector<int> res(q);
    vector<pair<i64, int>> qq(q);
    for (int i = 0; i < q; ++i) {
        cin >> qq[i].first;
        qq[i].second = i;
    }
    sort(all(qq));

    // for (int val : os) {
    //     cout << ord[val] << " ";
    // }
    // cout << endl;

    i64 cur = 0;
    int ptrq = 0;
    for (int i = 0; i < mx; ++i) {
        while (ptrq < q and qq[ptrq].first < cur + isz(os)) {
            auto needed = qq[ptrq].first - cur;
            // cout << i << " " << qq[ptrq].second << " " << needed << endl;
            res[qq[ptrq].second] = *os.find_by_order(needed);
            ++ptrq;
        }
        cur += isz(os);

        for (int u : av[i + 1]) {
            os.insert(tin[u]);
            int p = par[u];
            os.insert(oth[p][optr[p]++]);
        }

        // for (int val : os) {
        //     cout << ord[val] << " ";
        // }
        // cout << endl;
    }

    while (ptrq < q) {
        auto needed = (qq[ptrq].first - cur) % isz(os);
        res[qq[ptrq].second] = *os.find_by_order(needed);
        ++ptrq;
    }

    for (auto val : res) {
        cout << ord[val] + 1 << "\n";
    }

    // int ct = 0;
    // for (int i = 0; i < n; ++i) {
    //     ans << i << " " << d[i] << endl;
    //     ct += d[i] <= 1;
    // }
    // cout << ct << endl;
}

signed main() {

#ifndef CDuongg
    if (fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

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