Submission #1236517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236517		MarwenElarbi	Prize (CEOI22_prize)	C++20	0 / 100	766 ms	162204 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
const int nax = 5e5+5;
vector<int> adj[2][nax];
int parent[2][nax];
vector<pair<int,int>> tree[2][nax];
int cnt=0;
int n,k,q,t;
vector<pair<int,int>> euler(nax);
vector<pair<pair<int,int>,int>> inter;
int depth[2][nax];
int de[2][nax];
int bj[2][20][nax];
int root;
vector<int> answer;
vector<pair<int,int>> to_ask;
void dfs(int x,int p,int cnt){
    if(answer.size()<k&&p!=-1){
        answer.push_back(x);
        to_ask.push_back({x,p});
    }
    for(auto u:adj[0][x]){
        if(u==p) continue;
        dfs(u,x,cnt);
    } 
}
void compute(int x,int p,int cnt){
    for (int i = 1; i < 20; ++i)
    {
        bj[cnt][i][x]=bj[cnt][i-1][bj[cnt][i-1][x]];
    }
    for(auto u:tree[cnt][x]){
        if(u.fi==p) continue;
        depth[cnt][u.fi]=depth[cnt][x]+u.se;
        de[cnt][u.fi]=de[cnt][x]+1;
        bj[cnt][0][u.fi]=x;
        compute(u.fi,x,cnt);
    }
    return;
}
int jump(int x,int d,int cnt){
    for (int i = 0; i < 20; ++i)
    {
        if((1<<i)&d) x=bj[cnt][i][x];
    }
    return x;
}
int lca(int x,int y,int cnt){
    if(de[cnt][x]<de[cnt][y]) swap(x,y);
    x=jump(x,de[cnt][x]-de[cnt][y],cnt);
    if(x==y) return x;
    for (int i = 19; i >= 0; --i)
    {
        if(bj[cnt][i][x]!=bj[cnt][i][y]){
            y=bj[cnt][i][x];
            x=bj[cnt][i][y];
        }
    }
    return bj[cnt][0][x];
}
int main() {
    cin>>n>>k>>q>>t;
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin>>x;
        if(x!=-1){
            adj[0][x].pb(i);
            adj[0][i].pb(x);
        }else root=i;
    }
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin>>x;
    }
    bj[cnt][0][root]=root;
    answer.push_back(root);
    dfs(root,-1,0);
    for(auto u : answer) cout <<u<<" ";
        cout <<endl;
    for(auto u:to_ask){
        int a,b,c,d;
        cout << "? "<<u.fi<<" "<<u.se<<endl;
        cin>>a>>b>>c>>d;
        tree[0][u.fi].push_back({u.se,a});
        tree[0][u.se].push_back({u.fi,a});
    }
    compute(root,-1,0);
    cout <<"! "<<endl;
    while(t--){
        int a,b;
        cin>>a>>b;
        //cout <<depth[0][a]<<" "<<depth[0][b]<<endl;
        cout << depth[0][a]+depth[0][b]-2*depth[0][lca(a,b,0)] << " " << depth[0][a]+depth[0][b]-2*depth[0][lca(a,b,0)] <<endl;
    }
}

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