oj.uz

Submission #994354

# Submission time Handle Problem Language Result Execution time Memory
994354 2024-06-07T13:13:50 Z biank Prize (CEOI22_prize) C++14
0 / 100
 574 ms 152908 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(x) int(x.size())
#define all(x) begin(x),end(x)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dbg(x) cerr<<#x<<": "<<x<<endl

#define pb push_back

typedef vector<int> vi;

struct TreeData{
    vi depth,height;
    vector<vi> adj;
    vector<vi> up;
    int root,n,k,log;
    vi x;
    TreeData(int _n, int _k):depth(_n+1),height(_n+1),adj(_n+1){
        n=_n;
        log=32-__builtin_clz(n+1);
        up.assign(log,vi(n+1));
        root=0,k=_k;
    }
    void dfs(int u, int p=0){
        if(sz(x)>=k) return;
        x.pb(u);
        height[u]=height[p]+1;
        for(int v:adj[u]) if(v!=p) dfs(v,u);
    }
    void init(vi &tree){
        forn(i,n){
            up[0][i+1]=tree[i];
            if(tree[i]==0) root=i+1;
            adj[tree[i]].pb(i+1);
        }
        forn(i,log-1) forn(u,n+1){
            up[i+1][u]=up[i][up[i][u]];
        }
        height[0]=-1;
        dfs(root);
    }
    int lca(int u, int v){
        if(height[u]<height[v]) swap(u,v);
        int diff=height[u]-height[v];
        forn(i,log) if(diff>>i&1) u=up[i][u];
        if(u==v) return u;
        dforn(i,log) if(up[i][u]!=up[i][v]) u=up[i][u],v=up[i][v];
        return up[0][u];
    }
    int dist(int u, int v){
        //dbg(depth[u]);
        //dbg(depth[v]);
        //dbg(lca(u,v));
        //dbg(depth[lca(u,v)]);
        return depth[u]+depth[v]-2*depth[lca(u,v)];
    }
    void query(){
        forn(i,sz(x)){
            if(x[i]==root) continue;
            cout<<"? "<<root<<" "<<x[i]<<endl;
            int d[4];
            forn(j,4) cin>>d[j];
            depth[x[i]]=d[1];
        }
        cout<<"!"<<endl;
    }
};

int main(){
    int n,k,q,t;
    cin>>n>>k>>q>>t;
    vi tree[2];
    forn(i,2){
        tree[i].resize(n);
        forn(j,n){
            cin>>tree[i][j];
            if(tree[i][j]==-1){
                tree[i][j]=0;
            }
        }
    }
    TreeData ans(n,k);
    ans.init(tree[0]);
    forn(i,k) cout<<ans.x[i]<<' ';
    cout<<endl;
    ans.query();
    while(t--){
        int u,v;
        cin>>u>>v;
        int res=ans.dist(u,v);
        cout<<res<<" "<<res<<endl;
    }
    
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 257 ms 75440 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 265 ms 76524 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 247 ms 72688 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 522 ms 149068 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 574 ms 152908 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -