oj.uz

Submission #1016678

# Submission time Handle Problem Language Result Execution time Memory
1016678 2024-07-08T10:18:46 Z amine_aroua Prize (CEOI22_prize) C++17
0 / 100
 2798 ms 361412 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
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];
}
vector<int> ask(int a , int b)
{
    cout<<"? "<<a<<" "<<b<<endl;
    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;
    for(auto node : subset)
    {
        if(node != root[0])
        {
            dist[0][node] = ask(root[0] , node)[1];
        }
    }
    cout<<"!"<<endl;
    while(t--)
    {
        int u , v;
        cin>>u>>v;
        cout<<dist[0][u] + dist[0][v] - 2 * dist[0][lca(0 , u , v)]<<endl;
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1008 ms 180856 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1014 ms 181232 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 915 ms 180720 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2678 ms 360540 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2798 ms 361412 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -