oj.uz

Submission #732754

# Submission time Handle Problem Language Result Execution time Memory
732754 2023-04-29T09:03:59 Z loctildore Through Another Maze Darkly (CCO21_day1problem3) C++14
4 / 25
 1563 ms 414060 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
struct node {
    int l, r;
    node *lft, *rht;
    int tot;
    node(int tl, int tr): l(tl), r(tr), tot(0) {
        if (l + 1 == r) {
            lft = rht = NULL;
            return;
        }
        lft = new node(l, (l + r) / 2);
        rht = new node((l + r) / 2, r);
    }
    void add(int p) {
        if (p < l || p >= r) {
            return;
        }
        tot++;
        if (l + 1 == r) return;
        lft->add(p); rht->add(p);
    }
    int fnd(int x) {
        if (l + 1 == r) return l;
        if (lft->tot >= x) return lft->fnd(x);
        return rht->fnd(x - lft->tot);
    }
}* root;
int n, q;
int a, b, tb;
vector<int> grph[800069];
int lgc;
vector<int> lg[800069];
vector<pair<int,int>> vctr, qrys;
int ans[800069];
void dfs(int x, int rnd, int lst = -1) {
    for (auto i : grph[x]) {
        if (i == lst) {
            rnd++; continue;
        }
        vctr.push_back({i, rnd});
        dfs(i, rnd, x);
        vctr.push_back({x, rnd});
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin>>n>>q;
    for (int i = 0; i < n; i++) {
        cin>>a; cin>>tb; tb--;
        for (int j = 1; j < a; j++) {
            cin>>b; b--;
            grph[i].push_back(b);
        }
        grph[i].push_back(tb);
    }
    dfs(0, 0);
    root = new node(0, vctr.size());
    for (int i = 0; i < vctr.size(); i++) {
        vctr[i].f++;
        lg[vctr[i].s].push_back(i);
    }
    for (int i = 0; i < q; i++) {
        cin>>a;
        qrys.push_back({a, i});
    }
    sort(all(qrys));
    int cur = 0;
    for (auto tmp : qrys) {
        tie(a, b) = tmp;
        while (a - cur > root->tot && lgc < 800069) {
            cur += root->tot;
            for (auto i : lg[lgc]) {
                root->add(i);
            }
            lgc++;
        }
        a -= cur;
        a %= root->tot;
        if (!a) a = root->tot;
        ans[b] = vctr[root->fnd(a)].f;
    }
    for (int i = 0; i < q; i++) {
        cout<<ans[i]<<endl;
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:65:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < vctr.size(); i++) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37844 KB Output is correct
2 Correct 31 ms 42436 KB Output is correct
3 Correct 172 ms 83188 KB Output is correct
4 Correct 945 ms 397828 KB Output is correct
5 Correct 1563 ms 414060 KB Output is correct
6 Correct 1511 ms 411356 KB Output is correct
7 Correct 338 ms 105484 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 38028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 40992 KB Output is correct
2 Incorrect 53 ms 53744 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37844 KB Output is correct
2 Correct 31 ms 42436 KB Output is correct
3 Correct 172 ms 83188 KB Output is correct
4 Correct 945 ms 397828 KB Output is correct
5 Correct 1563 ms 414060 KB Output is correct
6 Correct 1511 ms 411356 KB Output is correct
7 Correct 338 ms 105484 KB Output is correct
8 Incorrect 21 ms 38028 KB Output isn't correct
9 Halted 0 ms 0 KB -