Submission #1192732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192732		Unforgettablepl	Prize (CEOI22_prize)	C++20	10 / 100	3551 ms	861560 KiB

Main

#define _GLIBCXX_DEBUG 1
#include <bits/stdc++.h>
using namespace std;

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,K,Q,T;
    cin >> N >> K >> Q >> T;
    vector<vector<int>> adj1(N+1);
    int root1;
    vector<vector<int>> adj2(N+1);
    int root2;
    for(int i=1;i<=N;i++){
        int p;cin>>p;
        if(p!=-1)adj1[p].emplace_back(i);
        else root1=i;
    }
    for(int i=1;i<=N;i++){
        int p;cin>>p;
        if(p!=-1)adj2[p].emplace_back(i);
        else root2=i;
    }
    // CHOOSE NODES
    vector<bool> choice(N+1);
    {
        int curr = 0;
        function<void(int)> dfs = [&](int x){
            if(curr<K){
                choice[x]=true;
                curr++;
                cout << x << ' ';
            }
            for(int&i:adj1[x])dfs(i);
        };
        dfs(root1);
        cout << endl;
    }
    // LCA setup
    vector lift1(N+1,vector<int>(20));
    vector<int> depth1(N+1);
    vector lift2(N+1,vector<int>(20));
    vector<int> depth2(N+1);
    {
        function<void(int,int,int)> dfs = [&](int x,int p,int dep){
            lift1[x][0]=p;
            depth1[x]=dep;
            for(int&i:adj1[x])dfs(i,x,dep+1);
        };
        dfs(root1,0,0);
    }
    {
        function<void(int,int,int)> dfs = [&](int x,int p,int dep){
            lift2[x][0]=p;
            depth2[x]=dep;
            for(int&i:adj2[x])dfs(i,x,dep+1);
        };
        dfs(root2,0,0);
    }
    {
        for(int bit=1;bit<=19;bit++){
            for(int i=1;i<=N;i++){
                lift1[i][bit]=lift1[lift1[i][bit-1]][bit-1];
                lift2[i][bit]=lift2[lift2[i][bit-1]][bit-1];
            }
        }
    }
    auto lca1 = [&](int a,int b){
        if(depth1[a]>depth1[b])swap(a,b);
        int target = depth1[b]-depth1[a];
        for(int bit=0;bit<=19;bit++)if(target&(1<<bit))
            b=lift1[b][bit];
        if(a==b)return a;
        for(int bit=19;bit>=0;bit--){
            if(lift1[a][bit]!=lift1[b][bit]){
                a = lift1[a][bit];
                b = lift1[b][bit];
            }
        }
        return lift1[a][0];
    };
    auto lca2 = [&](int a,int b){
        swap(depth1,depth2);
        swap(lift1,lift2);
        int ans = lca1(a,b);
        swap(depth1,depth2);
        swap(lift1,lift2);
        return ans;
    };
    vector<int> dfsOrder = {-1};
    vector<int> idx(N+1);
    {
        function<void(int)> dfs = [&](int x){
            for(int&i:adj2[x])dfs(i);
            if(choice[x]){
                idx[x]=dfsOrder.size();
                dfsOrder.emplace_back(x);
            }
        };
        dfs(root2);
    }
    vector<int> L(K+1);
    vector<int> R(K+1);
    vector<int> P(K+1);
    vector<int> idxOfLca(N+1);
    {
        for(int i=1;i<K;i++){
            idxOfLca[lca2(dfsOrder[i],dfsOrder[i+1])] = i;
            cout << "? " << dfsOrder[i] << ' ' << dfsOrder[i+1] << '\n';
        }
        cout << "!" << endl;
        for(int i=1;i<K;i++){
            int d1a,d1b,d2a,d2b;
            cin >> d1a >> d1b >> d2a >> d2b;
            // TODO process tree 1
            R[i] = d2a;
            L[i+1] = d2b;
            P[i]=P[i-1]+R[i]-L[i];
        }
        P[K]=P[K-1]+R[K]-L[K];
    }
    auto solve2 = [&](int a,int b){
        int origA = a;
        int origB = b;
        a = idx[a];
        b = idx[b];
        if(a>b)swap(a,b);
        if(a==b)return 0ll;
        int mid = idxOfLca[lca2(origA,origB)];
        if(mid<=b)return P[mid]-P[a]+R[a]-(P[b]-P[mid])+R[b];
        return P[mid]-P[a]+R[a]+P[mid]-P[b]+R[b];
    };
    {
        vector<pair<int,int>> queries(T);
        for(auto&[a,b]:queries)cin>>a>>b;
        for(auto&[a,b]:queries){
            // TODO answer for tree 1
            int ans1 = -1;
            int ans2 = solve2(a,b);
            ans1=ans2;
            cout << ans1 << ' ' << ans2 << '\n';
        }
    }
}

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