Submission #1016702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016702		amine_aroua	Prize (CEOI22_prize)	C++17	10 / 100	1976 ms	363084 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int n, k , q,t;
vector<vector<int>> adj[2];
int root[2];
vector<int> depth[2];
vector<int> dist[2];
vector<vector<int>> up[2];
void dfs(int i,int x)
{
    for(auto u : adj[i][x])
    {
        depth[i][u] = depth[i][x] + 1;
        up[i][0][u] = x;
        for(int j = 1 ; j < 20 ; j++)
        {
            up[i][j][u] = up[i][j - 1][up[i][j - 1][u]];
        }
        dfs(i , u);
    }
}
void lift(int i , int &u , int x)
{
    for(int j = 0 ; j < 20 ; j++)
        if((1<<j) & x)
            u = up[i][j][u];
}
int lca(int i ,int u , int v)
{
    if(depth[i][u] < depth[i][v])
        swap(u , v);
    int x = depth[i][u] - depth[i][v];
    lift(i , u , x);
    if(u == v)
        return u;
    for(int j = 19 ; j >= 0 ; j--)
    {
        int nu = up[i][j][u] , nv = up[i][j][v];
        if(nu == nv)
            continue;
        u = nu , v = nv;
    }
    return up[i][0][u];
}
void askO(int a , int b)
{
    cout<<"? "<<a<<" "<<b<<endl;
}
vector<int> askI(int a , int b)
{
    vector<int> ret(4);
    for(auto &x : ret)
        cin>>x;
    return ret;
}
int main() {
    cin>>n>>k>>q>>t;
    for(int i = 0 ; i < 2 ; i++)
    {
        adj[i].assign(n +1 , {});
        depth[i].assign(n + 1 , 0);
        dist[i].assign(n + 1 , 0);
        up[i].assign(20 , vector<int>(n + 1,  0));
    }
    for(int i = 0 ; i < 2 ; i++)
    {
        for(int j = 1; j <= n ; j++)
        {
            int x;
            cin>>x;
            if(x == -1)
            {
                root[i] = j;
                continue;
            }
            adj[i][x].push_back(j);
        }
        dfs(i , root[i]);
    }
    vector<int> subset;
    queue<int> Q;
    Q.push(root[0]);
    int cnt = 0;
    while (cnt < k)
    {
        int tp = Q.front();
        Q.pop();
        subset.push_back(tp);
        cnt++;
        for(auto u : adj[0][tp])
            Q.push(u);
    }
    for(auto node : subset)
    {
        cout<<node<<" ";
    }
    cout<<endl;
    cout.flush();
    for(auto node : subset)
    {
        if(node != root[0])
        {
            askO(root[0] , node);
        }
    }
    cout<<"!"<<endl;
    cout.flush();
    for(auto node : subset)
    {
        if(node != root[0])
            dist[0][node] = askI(root[0] , node)[1];
    }
    vector<pair<int ,int>> queries;
    while(t--)
    {
        int u , v;
        cin>>u>>v;
        queries.push_back({u , v});
    }
    for(auto [u , v] : queries)
    {
        cout<<dist[0][u] + dist[0][v] - 2 * dist[0][lca(0 , u , v)]<<" "<<dist[0][u] + dist[0][v] - 2 * dist[0][lca(0 , u , v)]<<endl;
    }
    cout.flush();
}

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