oj.uz

Submission #1016702

# Submission time Handle Problem Language Result Execution time Memory
1016702 2024-07-08T10:39:36 Z amine_aroua Prize (CEOI22_prize) C++17
10 / 100
 1976 ms 363084 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 182776 KB Output is correct
2 Correct 1063 ms 183176 KB Output is correct
3 Correct 885 ms 128808 KB Output is correct
4 Correct 818 ms 128592 KB Output is correct
5 Correct 786 ms 128772 KB Output is correct
6 Correct 1002 ms 140084 KB Output is correct
7 Correct 1181 ms 140164 KB Output is correct
8 Correct 1033 ms 140072 KB Output is correct
9 Correct 835 ms 128488 KB Output is correct
10 Correct 831 ms 128740 KB Output is correct
11 Correct 726 ms 128540 KB Output is correct
12 Correct 739 ms 128592 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 961 ms 182964 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 707 ms 181228 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1791 ms 362228 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1976 ms 363084 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -