oj.uz

Submission #1109835

# Submission time Handle Problem Language Result Execution time Memory
1109835 2024-11-07T17:44:06 Z omsincoconut Prize (CEOI22_prize) C++17
0 / 100
 1283 ms 537116 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 init_tree[2 * MAXN];
pii tree[8 * MAXN];

// Initialize all arrays to avoid undefined behavior
void initializeArrays() {
    fill_n(&P[0][0], 2 * MAXN, -1);
    fill_n(&root[0], 2, -1);
    for (int i = 0; i < 2; ++i) {
        ord[i].clear();
        fill_n(&tin[i][0], MAXN, 0);
        fill_n(&tout[i][0], MAXN, 0);
        fill_n(&depth[i][0], MAXN, 0);
        child[i]->clear();
    }
    fill_n(subtree_by_ord, MAXN, 0);
    fill_n(&init_tree[0], 2 * MAXN, make_pair(INT_MAX, INT_MAX));
    fill_n(&tree[0], 8 * MAXN, make_pair(INT_MAX, INT_MAX));
}

// Iterative DFS to avoid stack overflow
void dfs(int curtree, int start) {
    stack<pair<int, int>> stk;  // Pair of node and DFS state
    stk.push({start, 0});
    int cte = 0;
    
    while (!stk.empty()) {
        auto [u, state] = stk.top();
        stk.pop();

        if (state == 0) {
            tin[curtree][u] = ++cte;
            ord[curtree].push_back(u);
            if (curtree == 0) init_tree[cte] = make_pair(depth[curtree][u], u);
            
            stk.push({u, 1});  // Add state 1 for postorder actions
            for (int v : child[curtree][u]) {
                depth[curtree][v] = depth[curtree][u] + 1;
                stk.push({v, 0});  // Add children with state 0
            }
        } else {
            tout[curtree][u] = cte;
            if (curtree == 0) init_tree[++cte] = make_pair(depth[curtree][u], u);
        }
    }
}

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

    initializeArrays();  // Ensure all arrays are initialized to avoid segmentation faults

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

    ord[0].push_back(0);
    ord[1].push_back(1);

    depth[0][root[0]] = depth[1][root[1]] = 0;

    dfs(0, root[0]);
    dfs(1, root[1]);

    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 and results processing
    for (int i = 1; i <= T; i++) {
        int u = query[i][0], v = query[i][1];

        int uvlca = lca(0, u, v);
        cout << distdata[u] + distdata[v] - 2 * distdata[uvlca] << ' ';
        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';
    }

    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 19.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1283 ms 536448 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 1282 ms 537116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -