Submission #1192739

#TimeUsernameProblemLanguageResultExecution timeMemory
1192739UnforgettableplPrize (CEOI22_prize)C++20
76 / 100
3604 ms670760 KiB
#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);
    vector<vector<pair<int,int>>> newadj(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;
            {
                int lca = lca1(dfsOrder[i],dfsOrder[i+1]);
                newadj[lca].emplace_back(dfsOrder[i],d1a);
                newadj[dfsOrder[i]].emplace_back(lca,-d1a);
                newadj[lca].emplace_back(dfsOrder[i+1],d1b);
                newadj[dfsOrder[i+1]].emplace_back(lca,-d1b);
            }
            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];
    }
    vector<int> dist(N+1);
    {
        vector<bool> visited(N+1);
        function<void(int,int)> dfs = [&](int x,int curr){
            if(visited[x])return;
            visited[x]=true;
            dist[x]=curr;
            for(auto&[v,c]:newadj[x])dfs(v,curr+c);
        };
        dfs(root1,0);
    }
    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)];
        return P[mid]-P[a]+R[a]+P[mid]-P[b]+R[b];
    };
    auto solve1 = [&](int a,int b){
        int lca = lca1(a,b);
        return dist[b]+dist[a]-2*dist[lca];
    };
    {
        vector<pair<int,int>> queries(T);
        for(auto&[a,b]:queries)cin>>a>>b;
        for(auto&[a,b]:queries){
            int ans1 = solve1(a,b);
            int ans2 = solve2(a,b);
            cout << ans1 << ' ' << ans2 << '\n';
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...