Submission #861266

#	Time	Username	Problem	Language	Result	Execution time	Memory
861266		vgtcross	Prize (CEOI22_prize)	C++17	10 / 100	781 ms	98200 KiB

Main

#include <bits/stdc++.h>

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

const int N = int(5e5) + 1000;
const int K = 19;

vector<int> ch[N];
int jmp[K][N];
vector<int> st;
ll d[N], dis[N];
int k2;

void dfs(int u) {
    if (k2 && u) {
        st.push_back(u);
        --k2;
    }
    
    for (int v : ch[u]) {
        d[v] = d[u] + 1;
        dfs(v);
    }
}

void dfs2(int u) {
    for (int v : ch[u]) {
        dis[v] += dis[u];
        dfs2(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;
            if (i == 0) {
                ch[q].push_back(j);
                jmp[0][j] = q;
            }
        }
    }
    
    k2 = k;
    dfs(0);
    
    for (int i : st) cout << i << ' ';
    cout << endl;
    
    for (int i : st) if (jmp[0][i]) {
        cout << "? " << i << ' ' << jmp[0][i] << '\n';
    }
    cout << "!" << endl;
    
    for (int i : st) if (jmp[0][i]) {
        int a[4];
        for (int &j : a) cin >> j;
        dis[i] = a[0];
    }
    
    dfs2(0);
    
    for (int i = 1; i < K; ++i) {
        for (int j = 0; j <= n; ++j) {
            jmp[i][j] = jmp[i-1][jmp[i-1][j]];
        }
    }
    
    vector<pii> que(t);
    for (int i = 0; i < t; ++i) cin >> que[i].first >> que[i].second;
    
    for (int i = 0; i < t; ++i) {
        int a = que[i].first, b = que[i].second;
        ll base = dis[a] + dis[b];
        if (a == b) {
            cout << base - 2 * dis[a] << ' ' << base - 2 * dis[a] << '\n';
            continue;
        }
        
        if (d[a] < d[b]) swap(a, b);
        for (int i = K-1; i >= 0; --i) {
            if (d[jmp[i][a]] >= d[b]) a = jmp[i][a];
        }
        
        if (a == b) {
            cout << base - 2 * dis[a] << ' ' << base - 2 * dis[a] << '\n';
            continue;
        }
        
        for (int i = K-1; i >= 0; --i) {
            if (jmp[i][a] != jmp[i][b]) {
                a = jmp[i][a];
                b = jmp[i][b];
            }
        }
        
        a = jmp[0][a];
        cout << base - 2 * dis[a] << ' ' << base - 2 * dis[a] << '\n';
    }
    cout << flush;
}

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

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