oj.uz

답안 #725979

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
725979 2023-04-18T09:37:32 Z tengiz05 Prize (CEOI22_prize) C++17
0 / 100
 2996 ms 372044 KB 
#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1E6 + 5;

struct Tree {
    std::vector<int> adj[N];
    int up[N][20];
    int in[N], out[N];
    int timeStamp = 0;
    void dfs(int u, int p) {
        in[u] = timeStamp++;
        up[u][0] = p;
        for (int i = 1; i < 20; i++) {
            up[u][i] = up[up[u][i - 1]][i - 1];
        }
        for (int v : adj[u]) {
            dfs(v, u);
        }
        out[u] = timeStamp;
    }
    bool is(int u, int v) {
        return in[u] <= in[v] && in[v] < out[u];
    }
    int lca(int u, int v) {
        if (is(u, v)) return u;
        if (is(v, u)) return v;
        for (int i = 19; i >= 0; i--) {
            if (!is(up[u][i], v)) {
                u = up[u][i];
            }
        }
        return up[u][0];
    }
    std::vector<std::pair<int, int>> e[N];
    int sum[N];
    bool vis[N];
    void fill(int u) {
        vis[u] = true;
        for (auto [v, w] : e[u]) {
            if (vis[v]) continue;
            if (in[v] > in[u]) {
                sum[v] = sum[u] + w;
            } else {
                sum[v] = sum[u] - w;
            }
            fill(v);
        }
    }
} t1, t2;
/*

9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
0 6 13 0
3 0 0 5
2 7
7 1
1 2

*/
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k, q, T;
    std::cin >> n >> k >> q >> T;
    
    int r1 = -1, r2 = -1;
    for (int i = 0; i < n; i++) {
        int p;
        std::cin >> p;
        if (p == -1) r1 = i;
        else {
            p--;
            t1.adj[p].push_back(i);
        }
    }
    for (int i = 0; i < n; i++) {
        int p;
        std::cin >> p;
        if (p == -1) r2 = i;
        else {
            p--;
            t2.adj[p].push_back(i);
        }
    }
    t1.dfs(r1, r1);
    t2.dfs(r2, r2);
    
    std::vector<int> f{r1};
    if (r1 != r2) f.push_back(r2);
    for (int i = 0; int(f.size()) < k; i++) {
        if (i != r1 && i != r2) {
            f.push_back(i);
        }
    }
    std::sort(f.begin(), f.end());
    assert(std::unique(f.begin(), f.end()) == f.end());
    
    for (int i = 0; i < k; i++) {
        std::cout << f[i] + 1 << " \n"[i == k - 1];
    }
    for (int i = 0; i < k - 1; i++) {
        std::cout << "? " << f[i] + 1 << " " << f[i + 1] + 1 << "\n";
    }
    std::cout << "!" << std::endl;
    
    for (int i = 0; i < k - 1; i++) {
        int a = f[i];
        int b = f[i + 1];
        int l = t1.lca(a, b);
        int c1, c2;
        std::cin >> c1 >> c2;
        t1.e[a].emplace_back(l, c1);
        t1.e[l].emplace_back(a, c1);
        t1.e[b].emplace_back(l, c2);
        t1.e[l].emplace_back(b, c2);
        l = t2.lca(a, b);
        std::cin >> c1 >> c2;
        t2.e[a].emplace_back(l, c1);
        t2.e[l].emplace_back(a, c1);
        t2.e[b].emplace_back(l, c2);
        t2.e[l].emplace_back(b, c2);
    }
    
    t1.fill(r1);
    t2.fill(r2);
    
    std::vector<std::pair<int, int>> queries(T);
    for (auto &[a, b] : queries) {
        std::cin >> a >> b;
        a--;
        b--;
    }
    
    for (auto [a, b] : queries) {
        int l = t1.lca(a, b);
        std::cout << t1.sum[a] + t1.sum[b] - 2 * t1.sum[l] << " ";
        l = t2.lca(a, b);
        std::cout << t2.sum[a] + t2.sum[b] - 2 * t2.sum[l] << "\n";
    }
    std::cout.flush();
    
    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1248 ms 235904 KB Output is correct
2 Correct 1476 ms 238968 KB Output is correct
3 Runtime error 852 ms 207340 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1338 ms 238708 KB Output is correct
2 Correct 1200 ms 234240 KB Output is correct
3 Runtime error 835 ms 207252 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1489 ms 227816 KB Output is correct
2 Correct 1235 ms 227816 KB Output is correct
3 Runtime error 739 ms 197428 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2996 ms 361412 KB Output is correct
2 Correct 2688 ms 361428 KB Output is correct
3 Runtime error 1512 ms 300408 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2556 ms 372044 KB Output is correct
2 Correct 2532 ms 371364 KB Output is correct
3 Runtime error 1644 ms 309792 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -