제출 #1189423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1189423		Unforgettablepl	Prize (CEOI22_prize)	C++20	0 / 100	754 ms	199296 KiB

Main

#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<int> dfsOrder = {-1};
    vector<int> idx(N+1);
    {
        function<void(int)> dfs = [&](int x){
            if(choice[x]){
                idx[x]=dfsOrder.size();
                dfsOrder.emplace_back(x);
            }
            for(int&i:adj2[x])dfs(i);
        };
        dfs(root2);
    }
    vector<int> L(K+1);
    vector<int> R(K+1);
    vector<int> P(K+1);
    {
        for(int i=1;i<K;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){
        a = idx[a];
        b = idx[b];
        if(idx[a]>idx[b])swap(a,b);
        if(a==b)return 0ll;
        return R[a]+L[b]+P[b-1]-P[a];
    };
    {
        for(int i=1;i<=T;i++){
            int a,b;cin>>a>>b;
            // TODO answer for tree 1
            int ans1 = -1;
            int ans2 = solve2(a,b);
            ans1=ans2;
            cout << ans1 << ' ' << ans2 << '\n';
        }
    }
}

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