oj.uz

Submission #861262

# Submission time Handle Problem Language Result Execution time Memory
861262 2023-10-15T18:18:03 Z vgtcross Prize (CEOI22_prize) C++17
0 / 100
 291 ms 60684 KB 
#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 << '\n';
    
    for (int i : st) if (jmp[0][i]) {
        cout << "? " << i << ' ' << jmp[0][i] << 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]];
        }
    }
    
    cout << "!" << endl;
    while (t--) {
        int a, b;
        cin >> a >> b;
        ll base = dis[a] + dis[b];
        if (a == b) {
            cout << base - 2 * dis[a] << ' ' << base - 2 * dis[a] << endl;
            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] << endl;
            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] << endl;
    }
}

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 274 ms 60496 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 291 ms 60684 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 246 ms 59692 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

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