oj.uz

답안 #732798

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
732798 2023-04-29T10:04:11 Z loctildore Through Another Maze Darkly (CCO21_day1problem3) C++14
25 / 25
 1711 ms 450600 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) {
    vector<int> tmp[2];
    bool flag = false;
    for (auto i : grph[x]) {
        if (i == lst) {
            flag = true; continue;
        }
        tmp[flag].push_back(i);
    }
    for (auto i : tmp[1]) {
        vctr.push_back({i, rnd + 1});
        dfs(i, rnd + 1, x);
        vctr.push_back({x, rnd + 1});
    }
    for (auto i : tmp[0]) {
        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:75: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]
   75 |     for (int i = 0; i < vctr.size(); i++) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 37844 KB Output is correct
2 Correct 32 ms 42776 KB Output is correct
3 Correct 171 ms 86320 KB Output is correct
4 Correct 952 ms 416816 KB Output is correct
5 Correct 1537 ms 429176 KB Output is correct
6 Correct 1525 ms 426500 KB Output is correct
7 Correct 332 ms 103364 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 37972 KB Output is correct
2 Correct 25 ms 38092 KB Output is correct
3 Correct 21 ms 38376 KB Output is correct
4 Correct 22 ms 38604 KB Output is correct
5 Correct 23 ms 38460 KB Output is correct
6 Correct 22 ms 38692 KB Output is correct
7 Correct 22 ms 38584 KB Output is correct
8 Correct 22 ms 38600 KB Output is correct
9 Correct 21 ms 38636 KB Output is correct
10 Correct 23 ms 38768 KB Output is correct
11 Correct 24 ms 38688 KB Output is correct
12 Correct 24 ms 38904 KB Output is correct
13 Correct 23 ms 38768 KB Output is correct
14 Correct 23 ms 38700 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 41152 KB Output is correct
2 Correct 53 ms 54672 KB Output is correct
3 Correct 128 ms 74016 KB Output is correct
4 Correct 106 ms 68080 KB Output is correct
5 Correct 632 ms 276952 KB Output is correct
6 Correct 652 ms 274088 KB Output is correct
7 Correct 623 ms 273180 KB Output is correct
8 Correct 691 ms 284928 KB Output is correct
9 Correct 735 ms 329780 KB Output is correct
10 Correct 748 ms 349196 KB Output is correct
11 Correct 680 ms 400844 KB Output is correct
12 Correct 682 ms 398168 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 37844 KB Output is correct
2 Correct 32 ms 42776 KB Output is correct
3 Correct 171 ms 86320 KB Output is correct
4 Correct 952 ms 416816 KB Output is correct
5 Correct 1537 ms 429176 KB Output is correct
6 Correct 1525 ms 426500 KB Output is correct
7 Correct 332 ms 103364 KB Output is correct
8 Correct 20 ms 37972 KB Output is correct
9 Correct 25 ms 38092 KB Output is correct
10 Correct 21 ms 38376 KB Output is correct
11 Correct 22 ms 38604 KB Output is correct
12 Correct 23 ms 38460 KB Output is correct
13 Correct 22 ms 38692 KB Output is correct
14 Correct 22 ms 38584 KB Output is correct
15 Correct 22 ms 38600 KB Output is correct
16 Correct 21 ms 38636 KB Output is correct
17 Correct 23 ms 38768 KB Output is correct
18 Correct 24 ms 38688 KB Output is correct
19 Correct 24 ms 38904 KB Output is correct
20 Correct 23 ms 38768 KB Output is correct
21 Correct 23 ms 38700 KB Output is correct
22 Correct 24 ms 41152 KB Output is correct
23 Correct 53 ms 54672 KB Output is correct
24 Correct 128 ms 74016 KB Output is correct
25 Correct 106 ms 68080 KB Output is correct
26 Correct 632 ms 276952 KB Output is correct
27 Correct 652 ms 274088 KB Output is correct
28 Correct 623 ms 273180 KB Output is correct
29 Correct 691 ms 284928 KB Output is correct
30 Correct 735 ms 329780 KB Output is correct
31 Correct 748 ms 349196 KB Output is correct
32 Correct 680 ms 400844 KB Output is correct
33 Correct 682 ms 398168 KB Output is correct
34 Correct 315 ms 70532 KB Output is correct
35 Correct 384 ms 86764 KB Output is correct
36 Correct 607 ms 108260 KB Output is correct
37 Correct 1291 ms 319228 KB Output is correct
38 Correct 1367 ms 318700 KB Output is correct
39 Correct 1592 ms 320896 KB Output is correct
40 Correct 1593 ms 332356 KB Output is correct
41 Correct 1711 ms 384644 KB Output is correct
42 Correct 1708 ms 448896 KB Output is correct
43 Correct 1412 ms 450600 KB Output is correct
44 Correct 1412 ms 447712 KB Output is correct
45 Correct 1052 ms 385860 KB Output is correct
46 Correct 20 ms 37784 KB Output is correct