Submission #861256

#	Time	Username	Problem	Language	Result	Execution time	Memory
861256		vgtcross	Prize (CEOI22_prize)	C++17	0 / 100	956 ms	237220 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int N = int(1e6) + 1000;
const int K = 20;

vector<int> ch[2][N], ch2[2][N];
bool x[2][N];
int p[2][N];
int d[2][N];
int jmp[2][K][N];
stack<int> st;
int k2;

void dfs(int i, int u) {
    if (k2) {
        x[i][u] = 1;
        jmp[i][0][u] = p[i][u] = st.top() + (st.top() < 0);
        if (st.top() >= 0) ch2[i][st.top()].push_back(u);
        st.push(u);
        if (u > 0) --k2;
    }
    
    for (int v : ch[i][u]) dfs(i, v);
    
    if (x[i][u]) st.pop();
}

void dfs2(int i, int u) {
    for (int v : ch2[i][u]) {
        d[i][v] += d[i][u];
        dfs2(i, v);
    }
}

void solve() {
    int n, k, q, t;
    cin >> n >> k >> q >> t;
    
    for (int i = 0; i < 2; ++i) {
        for (int j = 1; j <= n; ++j) {
            int q;
            cin >> q;
            q += q < 0;
            ch[i][q].push_back(j);
        }
    }
    
    st.push(-1);
    k2 = k;
    dfs(0, 0);
    dfs(1, 0);
    
    for (int i = 1; i <= n; ++i) if (x[0][i]) cout << i << ' ';
    cout << endl;
    for (int i = 0; i < 1; ++i) {
        for (int j = 1; j <= n; ++j) if (x[i][j] && p[i][j]) {
            cout << "? " << j << ' ' << p[i][j] << endl;
            int a[4];
            for (int l = 0; l < 4; ++l) cin >> a[l];
            d[i][j] = a[2 * i];
        }
    }
    cout << "!" << endl;
    
    dfs2(0, 0);
    dfs2(1, 0);
    
    for (int l = 0; l < 2; ++l) {
        for (int i = 1; i < K; ++i) {
            for (int j = 0; j <= k; ++j) {
                jmp[l][i][j] = jmp[l][i-1][jmp[l][i-1][j]];
            }
        }
    }
    
    while (t--) {
        int aa, bb;
        cin >> aa >> bb;
        int c[2];
        for (int j = 0; j < 2; ++j) {
            int a = aa, b = bb;
            if (a == b) {
                c[j] = a;
                continue;
            }
            
            if (d[j][a] < d[j][b]) swap(a, b);
            for (int i = K-1; i >= 0; --i) {
                if (d[j][jmp[j][i][a]] >= d[j][b]) a = jmp[j][i][a];
            }
            
            if (a == b) {
                c[j] = a;
                continue;
            }
            
            for (int i = K-1; i >= 0; --i) {
                if (jmp[j][i][a] != jmp[j][i][b]) {
                    a = jmp[j][i][a];
                    b = jmp[j][i][b];
                }
            }
            
            c[j] = jmp[j][0][a];
        }
        
        for (int i = 0; i < 2; ++i) cout << d[0][aa] + d[0][bb] - 2 * d[0][c[0]] << ' ';
        cout << endl;
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    solve();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24