Submission #798912

#	Time	Username	Problem	Language	Result	Execution time	Memory
798912		math_rabbit_1028	Through Another Maze Darkly (CCO21_day1problem3)	C++14	25 / 25	1657 ms	269040 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, q;
vector<int> adj[808080];
int par[808080], ch[808080];
 
void get_par(int v, int p) {
    par[v] = p;
    for (int i = 0; i < adj[v].size(); i++) {
        int next = adj[v][i];
        if (ch[next]) continue;
        ch[next] = 1;
        get_par(next, v);
    }
}
 
vector<int> child[808080];
int order[2020202], visit[808080];
vector<int> upds[808080];
 
int r = -1;
void get_euler(int v) {
    order[++r] = v;
    upds[visit[v]].push_back(r);
    int f = 1;
    if (v == 1 || adj[v][0] == par[v]) f = 0;
    for (int i = 0; i < child[v].size(); i++) {
        int 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, int> query[808080];
int ans[808080];
int tree[8080808];
 
void update(int v, int st, int ed, int idx, int val) {
    if (st == idx && ed == idx) {
        tree[v] += val;
        return;
    }
    if (idx < st || idx > ed) return;
    int 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];
}
 
int get(int v, int st, int ed, int cnt) {
    if (st == ed) return st;
    int 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 (int i = 1; i <= n; i++) {
        int c, v;
        cin >> c;
        for (int j = 1; j <= c; j++) {
            cin >> v;
            adj[i].push_back(v);
        }
    }
 
    ch[1] = 1;
    get_par(1, 0);
 
    for (int j = 1; j < adj[1].size(); j++) {
        child[1].push_back(adj[1][j]);
    }
    child[1].push_back(adj[1][0]);
    for (int i = 2; i <= n; i++) {
        int k = 0;
        for (int j = 0; j < adj[i].size(); j++) {
            if (adj[i][j] == par[i]) {
                k = j;
                break;
            }
        }
        for (int j = k + 1; j < adj[i].size(); j++) child[i].push_back(adj[i][j]);
        for (int j = 0; j < k; j++) child[i].push_back(adj[i][j]);
    }
 
    visit[1] = 1;
    get_euler(1);
 
    for (int i = 1; i <= q; i++) {
        cin >> query[i].first;
        query[i].second = i;
    }
 
    sort(query + 1, query + q + 1);
 
    int p = 1; ll k = 0, sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int 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 (int i = p; i <= q; i++) {
        ans[query[i].second] = (query[i].first - k - 1) % sum + 1;
    }
 
    for (int i = 1; i <= q; i++) cout << order[ans[i]] << "\n";
 
    return 0;
}

Compilation message (stderr)

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

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