이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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=30;
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){
return depth[u]+depth[v]-2*depth[lca(u,v)];
}
void query(){
forn(i,sz(x)){
if(x[i]!=root) cout<<"? "<<root<<" "<<x[i]<<endl;
}
cout<<"!"<<endl;
forn(i,sz(x)){
if(x[i]==root){
depth[root]=0;
continue;
}
int d[4];
forn(j,4) cin>>d[j];
depth[x[i]]=d[1];
}
}
};
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();
vi res(t);
forn(i,t){
int u,v;
cin>>u>>v;
res[i]=ans.dist(u,v);
}
forn(i,t) cout<<res[i]<<' '<<res[i]<<'\n';
cout<<flush;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |