Submission #798712

#	Time	Username	Problem	Language	Result	Execution time	Memory
798712		math_rabbit_1028	Through Another Maze Darkly (CCO21_day1problem3)	C++14	4 / 25	1045 ms	283328 KiB

Main

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

ll n, q;
vector<ll> adj[808080];
ll par[808080], ch[808080];

void get_par(ll v, ll p) {
    par[v] = p;
    for (ll i = 0; i < adj[v].size(); i++) {
        ll next = adj[v][i];
        if (ch[next]) continue;
        ch[next] = 1;
        get_par(next, v);
    }
}

vector<ll> child[808080];
ll order[2020202], visit[808080];
vector<ll> upds[808080];

ll r = -1;
void get_euler(ll v) {
    order[++r] = v;
    upds[visit[v]].push_back(r);
    ll f = 1;
    if (v == 1 || adj[v][0] == par[v]) f = 0;
    for (ll i = 0; i < child[v].size(); i++) {
        ll next = child[v][i];
        visit[next] = visit[v] + f;
        get_euler(next);
        order[++r] = v;
        upds[visit[next]].push_back(r);
        if (next == adj[v][0]) f = 0;
    }
}

pair<ll, ll> query[808080];
ll ans[808080];
ll tree[8080808];

void update(ll v, ll st, ll ed, ll idx, ll val) {
    if (st == idx && ed == idx) {
        tree[v] += val;
        return;
    }
    if (idx < st || idx > ed) return;
    ll mid = (st + ed) / 2;
    update(2 * v, st, mid, idx, val);
    update(2 * v + 1, mid + 1, ed, idx, val);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
}

ll get(ll v, ll st, ll ed, ll cnt) {
    if (st == ed) return st;
    ll mid = (st + ed) / 2;
    if (tree[2 * v] >= cnt) return get(2 * v, st, mid, cnt);
    else return get(2 * v + 1, mid + 1, ed, cnt - tree[2 * v]);
}

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

    cin >> n >> q;
    for (ll i = 1; i <= n; i++) {
        ll c, v;
        cin >> c;
        for (ll j = 1; j <= c; j++) {
            cin >> v;
            adj[i].push_back(v);
        }
    }

    ch[1] = 1;
    get_par(1, 0);

    for (ll j = 0; j < adj[1].size(); j++) {
        child[1].push_back(adj[1][j]);
    }
    for (ll i = 2; i <= n; i++) {
        ll k = 0;
        for (ll j = 0; j < adj[i].size(); j++) {
            if (adj[i][j] == par[i]) {
                k = j;
                break;
            }
        }
        for (ll j = k + 1; j < adj[i].size(); j++) child[i].push_back(adj[i][j]);
        for (ll j = 0; j < k; j++) child[i].push_back(adj[i][j]);
    }

    visit[1] = 1;
    get_euler(1);

    for (ll i = 1; i <= q; i++) {
        cin >> query[i].first;
        query[i].second = i;
    }

    sort(query + 1, query + q + 1);

    ll p = 1; ll k = 0, sum = 0;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j < upds[i].size(); j++) {
            update(1, 1, 2*n-2, upds[i][j], 1);
            if (upds[i][j] > 0) sum += 1;
        }
        while (p <= q && query[p].first <= k + sum) {
            ans[query[p].second] = get(1, 1, 2*n-2, query[p].first - k);
            p++;
        }
        k += sum;
    }

    for (ll i = p; i <= q; i++) {
        ans[query[i].second] = (query[i].first - k - 1) % sum + 1;
    }

    for (ll i = 1; i <= q; i++) cout << order[ans[i]] << "\n";

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void get_par(ll, ll)':
Main.cpp:11:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (ll i = 0; i < adj[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void get_euler(ll)':
Main.cpp:29:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (ll i = 0; i < child[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:79:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (ll j = 0; j < adj[1].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
Main.cpp:84:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (ll j = 0; j < adj[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~
Main.cpp:90:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (ll j = k + 1; j < adj[i].size(); j++) child[i].push_back(adj[i][j]);
      |                            ~~^~~~~~~~~~~~~~~
Main.cpp:106:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for (ll j = 0; j < upds[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~

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