oj.uz

Submission #798912

# Submission time Handle Problem Language Result Execution time Memory
798912 2023-07-31T06:55:58 Z math_rabbit_1028 Through Another Maze Darkly (CCO21_day1problem3) C++14
25 / 25
 1657 ms 269040 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 57164 KB Output is correct
2 Correct 33 ms 59824 KB Output is correct
3 Correct 124 ms 82352 KB Output is correct
4 Correct 813 ms 248104 KB Output is correct
5 Correct 988 ms 263280 KB Output is correct
6 Correct 961 ms 255820 KB Output is correct
7 Correct 305 ms 102952 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 57300 KB Output is correct
2 Correct 33 ms 57344 KB Output is correct
3 Correct 32 ms 57392 KB Output is correct
4 Correct 32 ms 57572 KB Output is correct
5 Correct 32 ms 57536 KB Output is correct
6 Correct 32 ms 57548 KB Output is correct
7 Correct 32 ms 57496 KB Output is correct
8 Correct 34 ms 57668 KB Output is correct
9 Correct 32 ms 57584 KB Output is correct
10 Correct 32 ms 57588 KB Output is correct
11 Correct 33 ms 57680 KB Output is correct
12 Correct 33 ms 57760 KB Output is correct
13 Correct 32 ms 57684 KB Output is correct
14 Correct 32 ms 57688 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 58668 KB Output is correct
2 Correct 69 ms 64696 KB Output is correct
3 Correct 125 ms 73476 KB Output is correct
4 Correct 103 ms 69380 KB Output is correct
5 Correct 852 ms 147756 KB Output is correct
6 Correct 906 ms 149616 KB Output is correct
7 Correct 940 ms 152624 KB Output is correct
8 Correct 969 ms 158584 KB Output is correct
9 Correct 1150 ms 185404 KB Output is correct
10 Correct 1252 ms 204104 KB Output is correct
11 Correct 616 ms 239364 KB Output is correct
12 Correct 617 ms 230972 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 57164 KB Output is correct
2 Correct 33 ms 59824 KB Output is correct
3 Correct 124 ms 82352 KB Output is correct
4 Correct 813 ms 248104 KB Output is correct
5 Correct 988 ms 263280 KB Output is correct
6 Correct 961 ms 255820 KB Output is correct
7 Correct 305 ms 102952 KB Output is correct
8 Correct 30 ms 57300 KB Output is correct
9 Correct 33 ms 57344 KB Output is correct
10 Correct 32 ms 57392 KB Output is correct
11 Correct 32 ms 57572 KB Output is correct
12 Correct 32 ms 57536 KB Output is correct
13 Correct 32 ms 57548 KB Output is correct
14 Correct 32 ms 57496 KB Output is correct
15 Correct 34 ms 57668 KB Output is correct
16 Correct 32 ms 57584 KB Output is correct
17 Correct 32 ms 57588 KB Output is correct
18 Correct 33 ms 57680 KB Output is correct
19 Correct 33 ms 57760 KB Output is correct
20 Correct 32 ms 57684 KB Output is correct
21 Correct 32 ms 57688 KB Output is correct
22 Correct 38 ms 58668 KB Output is correct
23 Correct 69 ms 64696 KB Output is correct
24 Correct 125 ms 73476 KB Output is correct
25 Correct 103 ms 69380 KB Output is correct
26 Correct 852 ms 147756 KB Output is correct
27 Correct 906 ms 149616 KB Output is correct
28 Correct 940 ms 152624 KB Output is correct
29 Correct 969 ms 158584 KB Output is correct
30 Correct 1150 ms 185404 KB Output is correct
31 Correct 1252 ms 204104 KB Output is correct
32 Correct 616 ms 239364 KB Output is correct
33 Correct 617 ms 230972 KB Output is correct
34 Correct 250 ms 84752 KB Output is correct
35 Correct 283 ms 92412 KB Output is correct
36 Correct 379 ms 103164 KB Output is correct
37 Correct 1069 ms 175912 KB Output is correct
38 Correct 1165 ms 177828 KB Output is correct
39 Correct 1227 ms 181308 KB Output is correct
40 Correct 1319 ms 187568 KB Output is correct
41 Correct 1510 ms 218464 KB Output is correct
42 Correct 1657 ms 261824 KB Output is correct
43 Correct 911 ms 269040 KB Output is correct
44 Correct 927 ms 260620 KB Output is correct
45 Correct 1448 ms 225704 KB Output is correct
46 Correct 30 ms 57300 KB Output is correct