Submission #1109828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109828		omsincoconut	Prize (CEOI22_prize)	C++17	0 / 100	1404 ms	342568 KiB

Main

#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 init_tree[2*MAXN];
pii tree[8*MAXN];

void dfs(int curtree, int u, int &cte) {
    tin[curtree][u] = ++cte;
    ord[curtree].push_back(u);
    if (curtree == 0) init_tree[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) init_tree[cte] = make_pair(depth[curtree][u], u);
    }

    tout[curtree][u] = cte;
}

// Utility function to find minimum of two pairs
pii min_pair(const pii &a, const pii &b) {
    if (a.first < b.first || (a.first == b.first && a.second < b.second)) return a;
    return b;
}

// Build the segment tree
void build(int node, int start, int end) {
    if (start == end) {
        tree[node] = init_tree[start];
    } else {
        int mid = (start + end) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        tree[node] = min_pair(tree[2 * node], tree[2 * node + 1]);
    }
}

// Query the minimum in range [L, R]
pii qry(int node, int start, int end, int L, int R) {
    if (R < start || end < L) {
        return {INT_MAX, INT_MAX};  // return max pair (acts as neutral for min)
    }
    if (L <= start && end <= R) {
        return tree[node];
    }
    int mid = (start + end) / 2;
    pii left_min = qry(2 * node, start, mid, L, R);
    pii right_min = qry(2 * node + 1, mid + 1, end, L, R);
    return min_pair(left_min, right_min);
}

int lca(int curtree, int u, int v) {
    int l = tin[curtree][u], r = tin[curtree][v];
    if (l > r) swap(l, r);
    return qry(1, 1, 2*N, l, r).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 <= 2*N; i++) {
            init_tree[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);
    }

    build(1, 1, 2*N);

    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);

    // 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
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24