oj.uz

Submission #861266

# Submission time Handle Problem Language Result Execution time Memory
861266 2023-10-15T18:24:35 Z vgtcross Prize (CEOI22_prize) C++17
10 / 100
 781 ms 98200 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 << 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 98200 KB Output is correct
2 Correct 747 ms 98152 KB Output is correct
3 Correct 530 ms 66912 KB Output is correct
4 Correct 520 ms 67268 KB Output is correct
5 Correct 529 ms 66924 KB Output is correct
6 Correct 781 ms 74076 KB Output is correct
7 Correct 751 ms 73940 KB Output is correct
8 Correct 691 ms 73952 KB Output is correct
9 Correct 496 ms 66792 KB Output is correct
10 Correct 586 ms 67548 KB Output is correct
11 Correct 493 ms 66944 KB Output is correct
12 Correct 521 ms 67664 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 438 ms 97712 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 370 ms 96776 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

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