oj.uz

Submission #1109823

# Submission time Handle Problem Language Result Execution time Memory
1109823 2024-11-07T17:22:49 Z omsincoconut Prize (CEOI22_prize) C++17
0 / 100
 735 ms 402548 KB 
#include <bits/stdc++.h>

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

const int MAXN = 5e5+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[22][3*MAXN]; // used for lca query

void dfs(int curtree, int u, int &cte) {
    tin[curtree][u] = ++cte;
    ord[curtree].push_back(u);
    if (curtree == 0) table[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;
        if (curtree == 0) table[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[lg2][l], table[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];
int qc2[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][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 < 21; j++) {
        for (int i = 1; i <= 3*N-(1<<j); i++) {
            table[j+1][i] = min(table[j][i], table[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];
        if (tin[1][v] < tout[1][u]) {
            qc[tin[1][v]] += w1+w2;
            qc2[tout[1][u]] += w1+w2;
        } else {
            qc[tin[1][v]] += w1+w2;
        }
    }

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

    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 << uvlca << ':';
        cout << distdata[u] + distdata[v] - 2*distdata[uvlca] << ' ';
        // Tree 2;
        if (tin[1][u] > tin[1][v]) swap(u, v);
        if (tin[1][v] < tout[1][u])
            cout << qc[tin[1][v]] - qc[tin[1][u]] << '\n';
        else
            cout << qc[tin[1][v]] - qc2[tout[1][u]] << '\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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 400796 KB Output is correct
2 Correct 636 ms 402004 KB Output is correct
3 Runtime error 420 ms 346972 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 402548 KB Output is correct
2 Correct 633 ms 400536 KB Output is correct
3 Runtime error 438 ms 348488 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 398252 KB Output is correct
2 Correct 563 ms 386228 KB Output is correct
3 Runtime error 459 ms 333560 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 180 ms 87724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 157 ms 87716 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -