oj.uz

Submission #1102599

# Submission time Handle Problem Language Result Execution time Memory
1102599 2024-10-18T12:08:17 Z CDuong Through Another Maze Darkly (CCO21_day1problem3) C++17
25 / 25
 3169 ms 380364 KB 
/*
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 15 ms 4976 KB Output is correct
3 Correct 176 ms 46048 KB Output is correct
4 Correct 1869 ms 334376 KB Output is correct
5 Correct 2360 ms 380364 KB Output is correct
6 Correct 2209 ms 368352 KB Output is correct
7 Correct 323 ms 62384 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 564 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 3 ms 848 KB Output is correct
5 Correct 4 ms 848 KB Output is correct
6 Correct 3 ms 848 KB Output is correct
7 Correct 3 ms 848 KB Output is correct
8 Correct 3 ms 848 KB Output is correct
9 Correct 3 ms 1104 KB Output is correct
10 Correct 3 ms 1104 KB Output is correct
11 Correct 3 ms 1104 KB Output is correct
12 Correct 3 ms 1360 KB Output is correct
13 Correct 3 ms 1360 KB Output is correct
14 Correct 3 ms 1104 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3408 KB Output is correct
2 Correct 63 ms 16076 KB Output is correct
3 Correct 127 ms 33988 KB Output is correct
4 Correct 105 ms 26556 KB Output is correct
5 Correct 1208 ms 200364 KB Output is correct
6 Correct 1233 ms 202796 KB Output is correct
7 Correct 1304 ms 204724 KB Output is correct
8 Correct 1171 ms 216488 KB Output is correct
9 Correct 1435 ms 266012 KB Output is correct
10 Correct 1662 ms 295448 KB Output is correct
11 Correct 1348 ms 359292 KB Output is correct
12 Correct 1311 ms 347048 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 15 ms 4976 KB Output is correct
3 Correct 176 ms 46048 KB Output is correct
4 Correct 1869 ms 334376 KB Output is correct
5 Correct 2360 ms 380364 KB Output is correct
6 Correct 2209 ms 368352 KB Output is correct
7 Correct 323 ms 62384 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 564 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 3 ms 848 KB Output is correct
12 Correct 4 ms 848 KB Output is correct
13 Correct 3 ms 848 KB Output is correct
14 Correct 3 ms 848 KB Output is correct
15 Correct 3 ms 848 KB Output is correct
16 Correct 3 ms 1104 KB Output is correct
17 Correct 3 ms 1104 KB Output is correct
18 Correct 3 ms 1104 KB Output is correct
19 Correct 3 ms 1360 KB Output is correct
20 Correct 3 ms 1360 KB Output is correct
21 Correct 3 ms 1104 KB Output is correct
22 Correct 13 ms 3408 KB Output is correct
23 Correct 63 ms 16076 KB Output is correct
24 Correct 127 ms 33988 KB Output is correct
25 Correct 105 ms 26556 KB Output is correct
26 Correct 1208 ms 200364 KB Output is correct
27 Correct 1233 ms 202796 KB Output is correct
28 Correct 1304 ms 204724 KB Output is correct
29 Correct 1171 ms 216488 KB Output is correct
30 Correct 1435 ms 266012 KB Output is correct
31 Correct 1662 ms 295448 KB Output is correct
32 Correct 1348 ms 359292 KB Output is correct
33 Correct 1311 ms 347048 KB Output is correct
34 Correct 229 ms 23112 KB Output is correct
35 Correct 328 ms 37292 KB Output is correct
36 Correct 538 ms 55740 KB Output is correct
37 Correct 1467 ms 221404 KB Output is correct
38 Correct 1839 ms 223912 KB Output is correct
39 Correct 2163 ms 225728 KB Output is correct
40 Correct 2268 ms 234744 KB Output is correct
41 Correct 2485 ms 291488 KB Output is correct
42 Correct 3169 ms 368208 KB Output is correct
43 Correct 1904 ms 380028 KB Output is correct
44 Correct 1923 ms 368040 KB Output is correct
45 Correct 1768 ms 305832 KB Output is correct
46 Correct 1 ms 336 KB Output is correct