Submission #861291

#	Time	Username	Problem	Language	Result	Execution time	Memory
861291		vgtcross	Prize (CEOI22_prize)	C++17	0 / 100	875 ms	275444 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[2][N];
vector<array<int, 3>> ask[2];
bool x[N];
int d[2][N], dis[2][N];
int calc[2][N];
int jmp[2][K][N];

array<int, 2> dfs(int i, int u) {
    vector<array<int, 2>> vc, vc2;
    vector<int> vc1, vcf;
    for (int v : ch[i][u]) {
        auto a = dfs(i, v);
        if (a[0] != -1) vc.push_back(a);
    }
    
    if (u == 0) return {-1, -1};
    if (!x[u] && vc.size() == 0) return {-1, -1};
    else if (!x[u] && vc.size() == 1) return vc[0];
    else {
        for (auto a : vc) {
            if (a[1] != -1) vc2.push_back(a);
            else vc1.push_back(a[0]);
        }
        
        if (vc1.empty() && vc2.empty()) return {u, -1};
        
        if (vc1.size() == 1 && vc2.empty()) {
            if (jmp[i][0][u] == 0) {
                ask[i].push_back({vc1[0], u, u});
                return {-1, -1};
            } else return {u, vc1[0]};
        }
        
        if (vc1.empty() && vc2.size() == 1) {
            if (jmp[i][0][u] == 0) {
                ask[i].push_back({vc2[0][0], u, u});
                ask[i].push_back({vc2[0][1], u, u});
                return {-1, -1};
            } else {
                ask[i].push_back({vc2[0][0], u, u});
                return {u, vc2[0][1]};
            }
        }
        
        for (auto p : vc2) vcf.push_back(p[0]);
        for (auto p : vc1) vcf.push_back(p);
        for (auto p : vc2) vcf.push_back(p[1]);
        
        for (int j = 0; j+1 < vcf.size(); j += 2) ask[i].push_back({vcf[j], vcf[j+1], u});
        
        if (vcf.size() & 1) {
            if (jmp[i][0][u] == 0) {
                ask[i].push_back({vcf.back(), u, u});
                return {-1, -1};
            } else return {u, vcf.back()};
        } else return {u, -1};
    }
}

void dfs2(int i, int u) {
    if (calc[i][u] != -1) dis[i][u] += dis[i][calc[i][u]];
    for (int v : ch[i][u]) {
        d[i][v] = d[i][u] + 1;
        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;
            jmp[i][0][j] = q;
            ch[i][q].push_back(j);
            if (q == 0) x[j] = 1;
        }
    }
    
    int k2 = k-2;
    for (int i = 1; i <= n && k2; ++i) if (x[i] == 0) {
        x[i] = 1;
        --k2;
    }
    
    dfs(0, 0);
    dfs(1, 0);
    
    for (int i = 1; i <= n; ++i) if (x[i]) cout << i << ' ';
    cout << endl;
    for (int i = 0; i < 2; ++i) {
        for (auto a : ask[i]) {
            cout << "? " << a[0] << ' ' << a[1] << '\n';
        }
    }
    cout << "!" << endl;
    
    memset(calc, -1, sizeof calc);
    for (int i = 0; i < 2; ++i) {
        for (auto a : ask[i]) {
            int b[4];
            for (int &j : b) cin >> j;
            if (a[0] != a[2]) {
                dis[i][a[0]] = b[2*i];
                calc[i][a[0]] = a[2];
            }
            if (a[1] != a[2]) {
                dis[i][a[1]] = b[2*i + 1];
                calc[i][a[1]] = a[2];
            }
        }
    }
    
    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]];
            }
        }
    }
    
    vector<pii> que(t);
    for (pii &pr : que) cin >> pr.first >> pr.second;
    
    for (pii pr : que) {
        int aa = pr.first, bb = pr.second;
        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 << dis[i][aa] + dis[i][bb] - 2 * dis[i][c[i]] << ' ';
        cout << '\n';
    }
    cout << endl;
}

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

Compilation message (stderr)

Main.cpp: In function 'std::array<int, 2> dfs(int, int)':
Main.cpp:58:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int j = 0; j+1 < vcf.size(); j += 2) ask[i].push_back({vcf[j], vcf[j+1], u});
      |                         ~~~~^~~~~~~~~~~~

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