oj.uz

답안 #1107226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1107226 2024-11-01T03:29:30 Z Sharky Prize (CEOI22_prize) C++17
100 / 100
 1910 ms 390592 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 20;
const int LG = 20;

vector<int> node;

struct Tree {
    int n, rt, timer = 0, lift[N][LG], p[N], dep[N], tin[N], ps[N];
    vector<int> adj[N];
    vector<pair<int, int>> g[N];
    int jump(int sta, int dist) {
        for (int i = LG - 1; i >= 0; i--) 
            if ((1 << i) & dist) sta = lift[sta][i];
        return sta;
    }
    int lca(int x, int y) {
        if (dep[x] < dep[y]) swap(x, y);
        x = jump(x, dep[x] - dep[y]);
        if (x == y) return x;
        for (int i = LG - 1; i >= 0; i--) {
            int xt = lift[x][i], yt = lift[y][i];
            if (xt != yt) x = xt, y = yt;
        }
        return lift[x][0];
    }
    void dfs(int u, int pa, int k, bool pushing = 0) {
        tin[u] = ++timer;
        for (int i = 1; i < LG; i++) lift[u][i] = lift[lift[u][i-1]][i-1];
        if (pushing && (int) node.size() < k) node.push_back(u);
        for (int v : adj[u]) {
            if (v == pa) continue;
            lift[v][0] = u;
            dep[v] = dep[u] + 1;
            dfs(v, u, k, pushing);
        }
    }
    void init(int _n, int k, bool pushing = 0) {
        n = _n;
        for (int i = 1; i <= n; i++) {
            cin >> p[i];
            if (p[i] != -1) adj[p[i]].push_back(i);
            else rt = i;
        }
        lift[rt][0] = rt;
        dfs(rt, -1, k, pushing);
    }
    void add(int u, int v, int w) {
        g[u].push_back({v, w});
        g[v].push_back({u, -w});
    }
    void solve(int sc) {
        queue<int> bfs;
        ps[sc] = 1;
        bfs.push(sc);
        while (!bfs.empty()) {
            int u = bfs.front();
            bfs.pop();
            for (auto& [v, w] : g[u]) if (!ps[v]) {
                ps[v] = ps[u] + w;
                bfs.push(v);
            }
        }
    }
    int get_ans(int u, int v) {
        return ps[u] + ps[v] - ps[lca(u, v)] * 2;
    }
} S, T; // cont, non-cont

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k, q, t;
    cin >> n >> k >> q >> t;
    S.init(n, k, 1); T.init(n, k, 0);
    sort(node.begin(), node.end(), [&] (int x, int y) {
        return T.tin[x] < T.tin[y];
    });
    // assert((int) node.size() == k);
    for (int i = 0; i < k; i++) {
        cout << node[i];
        if (i == k - 1) cout << endl;
        else cout << ' ';
    }
    for (int i = 1; i < k; i++) cout << "? " << node[i-1] << " " << node[i] << '\n';
    cout << '!' << endl;
    int LCA = node[0];
    for (int i = 1; i < k; i++) {
        int lcas = S.lca(node[i-1], node[i]);
        int lcat = T.lca(node[i-1], node[i]);
        LCA = T.lca(LCA, node[i]);
        int su, sv, tu, tv;
        cin >> su >> sv >> tu >> tv;
        S.add(lcas, node[i-1], su); S.add(lcas, node[i], sv);
        T.add(lcat, node[i-1], tu); T.add(lcat, node[i], tv);
    }
    S.solve(S.rt); T.solve(LCA);
    vector<pair<int, int>> que;
    while (t--) {
        int u, v;
        cin >> u >> v;
        que.push_back({u, v});
    }
    for (auto& [u, v] : que) cout << S.ps[u] + S.ps[v] - S.ps[S.lca(u, v)] * 2 << " " << T.ps[u] + T.ps[v] - T.ps[T.lca(u, v)] * 2 << '\n';
    cout.flush();
}

/*
10 0 0 1
0 3 13 5
4 2
2 1
4 1
*/

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 873 ms 259216 KB Output is correct
2 Correct 975 ms 262276 KB Output is correct
3 Correct 591 ms 227256 KB Output is correct
4 Correct 623 ms 226600 KB Output is correct
5 Correct 673 ms 229804 KB Output is correct
6 Correct 896 ms 235500 KB Output is correct
7 Correct 976 ms 234972 KB Output is correct
8 Correct 863 ms 234820 KB Output is correct
9 Correct 661 ms 227140 KB Output is correct
10 Correct 733 ms 228052 KB Output is correct
11 Correct 557 ms 226168 KB Output is correct
12 Correct 689 ms 228352 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1077 ms 261480 KB Output is correct
2 Correct 937 ms 257668 KB Output is correct
3 Correct 589 ms 227400 KB Output is correct
4 Correct 698 ms 229908 KB Output is correct
5 Correct 670 ms 228396 KB Output is correct
6 Correct 772 ms 234700 KB Output is correct
7 Correct 1096 ms 236456 KB Output is correct
8 Correct 919 ms 236320 KB Output is correct
9 Correct 752 ms 234544 KB Output is correct
10 Correct 731 ms 235800 KB Output is correct
11 Correct 686 ms 232644 KB Output is correct
12 Correct 783 ms 237004 KB Output is correct

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 581 ms 251180 KB Output is correct
2 Correct 570 ms 250792 KB Output is correct
3 Correct 368 ms 218572 KB Output is correct
4 Correct 422 ms 218360 KB Output is correct
5 Correct 405 ms 218712 KB Output is correct
6 Correct 564 ms 225988 KB Output is correct
7 Correct 518 ms 226236 KB Output is correct
8 Correct 487 ms 226036 KB Output is correct
9 Correct 530 ms 223360 KB Output is correct
10 Correct 521 ms 224020 KB Output is correct
11 Correct 434 ms 223992 KB Output is correct
12 Correct 515 ms 224464 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1476 ms 379848 KB Output is correct
2 Correct 1509 ms 379736 KB Output is correct
3 Correct 961 ms 314840 KB Output is correct
4 Correct 1035 ms 314952 KB Output is correct
5 Correct 1045 ms 314848 KB Output is correct
6 Correct 1382 ms 329800 KB Output is correct
7 Correct 1255 ms 330400 KB Output is correct
8 Correct 1180 ms 329452 KB Output is correct
9 Correct 1181 ms 326384 KB Output is correct
10 Correct 1236 ms 325472 KB Output is correct
11 Correct 1115 ms 326380 KB Output is correct
12 Correct 1217 ms 325352 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1910 ms 390592 KB Output is correct
2 Correct 1776 ms 390152 KB Output is correct
3 Correct 1407 ms 323140 KB Output is correct
4 Correct 1442 ms 326584 KB Output is correct
5 Correct 1393 ms 322084 KB Output is correct
6 Correct 1597 ms 341692 KB Output is correct
7 Correct 1698 ms 337240 KB Output is correct
8 Correct 1577 ms 339604 KB Output is correct
9 Correct 1486 ms 335672 KB Output is correct
10 Correct 1511 ms 333928 KB Output is correct
11 Correct 1336 ms 334384 KB Output is correct
12 Correct 1778 ms 335900 KB Output is correct