oj.uz

답안 #635882

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
635882 2022-08-27T09:10:28 Z phathnv Through Another Maze Darkly (CCO21_day1problem3) C++11
25 / 25
 1322 ms 319336 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e6 + 10;

int n, q, timer;
vector<int> adj[N];
vector<array<int, 2>> phase[N];

void dfs(int u, int p, int t) {
    phase[t].push_back({++timer, u});

    bool mark = false;
    for (int v : adj[u]) {
        if (v == p) {
            mark = true;
            continue;
        }
        if (mark) {
            dfs(v, u, t + 1);
            phase[t + 1].push_back({++timer, u});
        }
    }
    for (int v : adj[u]) {
        if (v == p) {
            break;
        }
        dfs(v, u, t);
        phase[t].push_back({++timer, u});
    }
}

struct SegTree {
    int n;
    vector<int> cnt, val;
    void init(int _n) {
        n = _n;
        cnt.assign(n * 4 + 1, 0);
        val.assign(n + 1, 0);
    }
    void setVal(int id, int l, int r, int pos, int x) {
        if (pos < l || r < pos) {
            return;
        }
        if (l == r) {
            assert(val[l] == 0);
            val[l] = x;
            cnt[id] = 1;
            return;
        }
        int mid = (l + r) >> 1;
        setVal(id << 1, l, mid, pos, x);
        setVal(id << 1 | 1, mid + 1, r, pos, x);
        cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
    }
    int getKth(int id, int l, int r, int k) {
        if (cnt[id] < k) {
            return 0;
        }
        if (l == r) {
            assert(k == 1 && val[l] != 0);
            return val[l];
        }
        int mid = (l + r) >> 1;
        int ans = getKth(id << 1, l, mid, k);
        if (ans == 0) {
            ans = getKth(id << 1 | 1, mid + 1, r, k - cnt[id << 1]);
        }
        assert(ans != 0);
        return ans;
    }

    void setVal(int pos, int val) {
        assert(1 <= pos && pos <= n && val > 0);
        setVal(1, 1, n, pos, val);
    }
    int getKth(int k) {
        assert(k >= 1);
        int ans = getKth(1, 1, n, k);
        assert(ans != 0);
        return ans;
    }
} ST;

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

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k;
        adj[i].resize(k);
        for (auto &x : adj[i]) {
            cin >> x;
        }
        rotate(adj[i].begin(), adj[i].begin() + 1, adj[i].end());
    }

    dfs(1, -1, 0);

//    for (int i = 0; i < n; ++i) {
//        cerr << "phase " << i << endl;
//        for (auto [t, u] : phase[i]) {
//            cerr << t << ' ' << u << endl;
//        }
//    }

    vector<int> ans(q);
    vector<array<long long, 2>> queries(q);
    for (int i = 0; i < q; ++i) {
        cin >> queries[i][0];
        queries[i][1] = i;
    }
    sort(queries.begin(), queries.end());

    ST.init(timer);
    long long sum = 0;
    int cnt = 0, p = 0;
    for (auto [k, ind] : queries) {
        ++k;
        while (p < n) {
            if (sum + cnt < k) {
                sum += max(0, cnt - 1);
                for (auto [pos, val] : phase[p]) {
                    ST.setVal(pos, val);
                    ++cnt;
                }
                ++p;
            } else {
                k -= sum;
                ans[ind] = ST.getKth(k);
                break;
            }
        }
        if (!ans[ind]) {
            k -= sum;
            ans[ind] = ST.getKth((k - 1) % (cnt - 1) + 1);
        }
    }

    for (auto x : ans) {
        cout << x << '\n';
    }

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:120:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |     for (auto [k, ind] : queries) {
      |               ^
Main.cpp:125:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |                 for (auto [pos, val] : phase[p]) {
      |                           ^

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 94144 KB Output is correct
2 Correct 56 ms 96928 KB Output is correct
3 Correct 152 ms 121628 KB Output is correct
4 Correct 890 ms 303088 KB Output is correct
5 Correct 1172 ms 319336 KB Output is correct
6 Correct 1178 ms 316628 KB Output is correct
7 Correct 365 ms 142048 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 94280 KB Output is correct
2 Correct 54 ms 94268 KB Output is correct
3 Correct 49 ms 94452 KB Output is correct
4 Correct 53 ms 94484 KB Output is correct
5 Correct 52 ms 94432 KB Output is correct
6 Correct 47 ms 94428 KB Output is correct
7 Correct 60 ms 94412 KB Output is correct
8 Correct 47 ms 94504 KB Output is correct
9 Correct 54 ms 94540 KB Output is correct
10 Correct 67 ms 94652 KB Output is correct
11 Correct 54 ms 94620 KB Output is correct
12 Correct 48 ms 94704 KB Output is correct
13 Correct 48 ms 94668 KB Output is correct
14 Correct 46 ms 94600 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 95716 KB Output is correct
2 Correct 67 ms 101836 KB Output is correct
3 Correct 156 ms 111144 KB Output is correct
4 Correct 106 ms 105712 KB Output is correct
5 Correct 455 ms 177184 KB Output is correct
6 Correct 461 ms 177236 KB Output is correct
7 Correct 490 ms 181688 KB Output is correct
8 Correct 490 ms 191052 KB Output is correct
9 Correct 585 ms 227720 KB Output is correct
10 Correct 1026 ms 245896 KB Output is correct
11 Correct 515 ms 288028 KB Output is correct
12 Correct 518 ms 285452 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 94144 KB Output is correct
2 Correct 56 ms 96928 KB Output is correct
3 Correct 152 ms 121628 KB Output is correct
4 Correct 890 ms 303088 KB Output is correct
5 Correct 1172 ms 319336 KB Output is correct
6 Correct 1178 ms 316628 KB Output is correct
7 Correct 365 ms 142048 KB Output is correct
8 Correct 46 ms 94280 KB Output is correct
9 Correct 54 ms 94268 KB Output is correct
10 Correct 49 ms 94452 KB Output is correct
11 Correct 53 ms 94484 KB Output is correct
12 Correct 52 ms 94432 KB Output is correct
13 Correct 47 ms 94428 KB Output is correct
14 Correct 60 ms 94412 KB Output is correct
15 Correct 47 ms 94504 KB Output is correct
16 Correct 54 ms 94540 KB Output is correct
17 Correct 67 ms 94652 KB Output is correct
18 Correct 54 ms 94620 KB Output is correct
19 Correct 48 ms 94704 KB Output is correct
20 Correct 48 ms 94668 KB Output is correct
21 Correct 46 ms 94600 KB Output is correct
22 Correct 46 ms 95716 KB Output is correct
23 Correct 67 ms 101836 KB Output is correct
24 Correct 156 ms 111144 KB Output is correct
25 Correct 106 ms 105712 KB Output is correct
26 Correct 455 ms 177184 KB Output is correct
27 Correct 461 ms 177236 KB Output is correct
28 Correct 490 ms 181688 KB Output is correct
29 Correct 490 ms 191052 KB Output is correct
30 Correct 585 ms 227720 KB Output is correct
31 Correct 1026 ms 245896 KB Output is correct
32 Correct 515 ms 288028 KB Output is correct
33 Correct 518 ms 285452 KB Output is correct
34 Correct 383 ms 121620 KB Output is correct
35 Correct 395 ms 129804 KB Output is correct
36 Correct 482 ms 141212 KB Output is correct
37 Correct 987 ms 206164 KB Output is correct
38 Correct 1008 ms 205140 KB Output is correct
39 Correct 1096 ms 209992 KB Output is correct
40 Correct 1151 ms 219644 KB Output is correct
41 Correct 1278 ms 262416 KB Output is correct
42 Correct 1322 ms 316832 KB Output is correct
43 Correct 1004 ms 318308 KB Output is correct
44 Correct 1014 ms 315412 KB Output is correct
45 Correct 883 ms 265192 KB Output is correct
46 Correct 49 ms 94224 KB Output is correct