oj.uz

Submission #1109811

# Submission time Handle Problem Language Result Execution time Memory
1109811 2024-11-07T16:29:27 Z omsincoconut Prize (CEOI22_prize) C++17
10 / 100
 1572 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int MAXN = 1e6+5;

int N, K, Q, T;

// Tree information
int P[2][MAXN], root[2];
vector<int> child[2][MAXN];

vector<int> ord[2];
int tin[2][MAXN], tout[2][MAXN], depth[2][MAXN];

int subtree_by_ord[MAXN];
pii table[2][20][3*MAXN]; // used for lca query

void dfs(int curtree, int u, int &cte) {
    tin[curtree][u] = ++cte;
    ord[curtree].push_back(u);
    table[curtree][0][cte] = make_pair(depth[curtree][u], u);

    for (int v : child[curtree][u]) {
        depth[curtree][v] = depth[curtree][u] + 1;
        dfs(curtree, v, cte);
        ++cte;
        table[curtree][0][cte] = make_pair(depth[curtree][u], u);
    }

    tout[curtree][u] = ++cte;
}

int lca(int curtree, int u, int v) {
    int l = tin[curtree][u], r = tin[curtree][v];
    if (l > r) swap(l, r);
    int lg2 = 31 - __builtin_clz(r-l+1);
    return min(table[curtree][lg2][l], table[curtree][lg2][r-(1<<lg2)+1]).second;
}

bool sort_by_ord1(int u, int v) {
    return tin[1][u] < tin[1][v];
}

// Answer recovery
int result[2][MAXN][2];

// Equation graph for tree 1
int distdata[MAXN];
vector<pii> recov_edge[MAXN];

void recover_dfs(int u) {
    for (auto [v, w] : recov_edge[u]) {
        if (distdata[v] == -1) {
            distdata[v] = distdata[u] + w;
            recover_dfs(v);
        }
    }
}

// Euler tour quicksum for tree 2
int qc[3*MAXN];

// Queries
int query[MAXN][2];

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

    cin >> N >> K >> Q >> T;

    for (int i = 1; i <= N; i++) cin >> P[0][i];
    for (int i = 1; i <= N; i++) cin >> P[1][i];

    for (int i = 1; i <= N; i++) {
        if (P[0][i] != -1) child[0][P[0][i]].push_back(i);
        else root[0] = i;
        if (P[1][i] != -1) child[1][P[1][i]].push_back(i);
        else root[1] = i;
    }

    // Change to 1-based index
    ord[0].push_back(0);
    ord[1].push_back(1);

    {
        for (int i = 0; i <= 3*N; i++) {
            table[0][0][i] = table[1][0][i] = make_pair(INT_MAX, INT_MAX);
        }
        depth[0][root[0]] = depth[1][root[1]] = 0;
        int cte = 0;
        dfs(0, root[0], cte);
        cte = 0;
        dfs(1, root[1], cte);
    }

    for (int i = 1; i <= K; i++) subtree_by_ord[i] = ord[0][i];
    sort(subtree_by_ord+1, subtree_by_ord+K+1, sort_by_ord1);

    for (int j = 0; j < 19; j++) {
        for (int i = 1; i <= 3*N-(1<<j); i++) {
            table[0][j+1][i] = min(table[0][j][i], table[0][j][i+(1<<j)]);
            table[1][j+1][i] = min(table[1][j][i], table[1][j][i+(1<<j)]);
        }
    }

    // Query
    for (int i = 1; i <= K; i++) cout << subtree_by_ord[i] << " ";
    cout << "\n";
    for (int i = 1; i < K; i++) {
        cout << "? " << subtree_by_ord[i] << " " << subtree_by_ord[i+1] << "\n";
    }
    cout << "!" << endl;

    for (int i = 1; i < K; i++) {
        cin >> result[0][i][0] >> result[0][i][1] >> result[1][i][0] >> result[1][i][1];
    }

    // Tree 1 answer recovery
    for (int i = 1; i < K; i++) {
        int u = subtree_by_ord[i], v = subtree_by_ord[i+1], w1 = result[0][i][0], w2 = result[0][i][1];
        int uvlca = lca(0, u, v);
        recov_edge[uvlca].emplace_back(u, w1);
        recov_edge[u].emplace_back(uvlca, -w1);
        recov_edge[uvlca].emplace_back(v, w2);
        recov_edge[v].emplace_back(uvlca, -w2);
    }
    fill(distdata+1, distdata+N+1, -1);
    distdata[root[0]] = 0;
    recover_dfs(root[0]);

    // Tree 2 answer recovery
    for (int i = 1; i < K; i++) {
        int u = subtree_by_ord[i], v = subtree_by_ord[i+1], w1 = result[1][i][0], w2 = result[1][i][1];
        qc[tin[1][u]] += w1;
        qc[tout[1][u]] -= w1;
        qc[tin[1][v]] += w2;
        qc[tout[1][v]] -= w2;
    }

    for (int i = 1; i <= 3*N; i++) qc[i] += qc[i-1];

    for (int i = 1; i <= T; i++) cin >> query[i][0] >> query[i][1];

    for (int i = 1; i <= T; i++) {
        int u = query[i][0], v = query[i][1];

        // Tree 1
        int uvlca = lca(0, u, v);
        cout << distdata[u] + distdata[v] - 2*distdata[uvlca] << ' ';
        // Tree 2;
        cout << distdata[u] + distdata[v] - 2*distdata[uvlca] << '\n';
        //cout << qc[max(tin[1][u], tin[1][v])] - qc[min(tin[1][u], tin[1][v])] << '\n';
    }

    cout << endl;

    return 0;
}

/*
9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
*/

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1046 ms 650644 KB Output is correct
2 Correct 1039 ms 652972 KB Output is correct
3 Correct 852 ms 589424 KB Output is correct
4 Correct 831 ms 588888 KB Output is correct
5 Correct 911 ms 592208 KB Output is correct
6 Correct 979 ms 604628 KB Output is correct
7 Correct 956 ms 602852 KB Output is correct
8 Correct 1006 ms 602096 KB Output is correct
9 Correct 899 ms 588960 KB Output is correct
10 Correct 839 ms 590172 KB Output is correct
11 Correct 776 ms 589640 KB Output is correct
12 Correct 828 ms 590384 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 917 ms 652820 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 785 ms 645828 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1572 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1470 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -