This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int N = 5e5 + 5;
const int LOG = 20;
int n,q,k,t;
vector<int> v[N][2],g[N][2];
int depth[N][2],up[N][LOG][2],in[N][2],out[N][2],R[2];
int par[N][2],r[2],tin[N][2],tout[N][2],lift[N][LOG][2],ti=0;
void dfs(int c,int u){
tin[c][u]=++ti;
for(int i=1;i<LOG;i++) lift[c][i][u]=lift[lift[c][i-1][u]][i-1][u];
for(int x:v[c][u]){
if(x==par[c][u]) continue;
dfs(x,u);
}
tout[c][u]=ti;
}
void dfs2(int c,int u){
in[c][u]=++ti;
for(int i=1;i<LOG;i++) up[c][i][u]=up[up[c][i-1][u]][i-1][u];
for(int x:g[c][u]) dfs2(x,u);
out[c][u]=ti;
}
inline bool is_anc(int a,int b,int u){
return tin[a][u]<=tin[b][u] && tout[b][u]<=tout[a][u];
}
inline int lca(int a,int b,int u){
if(tin[a][u]>=tin[b][u]) swap(a,b);
if(is_anc(a,b,u)) return a;
for(int i=LOG-1;i>=0;i--){
if(!lift[a][i][u]) continue;
if(!is_anc(lift[a][i][u],b,u)) a=lift[a][i][u];
}
return lift[a][0][u];
}
inline bool Vis_anc(int a,int b,int u){
return in[a][u]<=in[b][u] && out[b][u]<=out[a][u];
}
inline int Vlca(int a,int b,int u){
if(in[a][u]>=in[b][u]) swap(a,b);
if(Vis_anc(a,b,u)) return a;
for(int i=LOG-1;i>=0;i--){
if(!up[a][i][u]) continue;
if(!Vis_anc(up[a][i][u],b,u)) a=up[a][i][u];
}
return up[a][0][u];
}
inline int dist(int a,int b,int u){
return depth[a][u]+depth[b][u]-2*depth[Vlca(a,b,u)][u];
}
inline array<int,2> Answer(int a,int b){
return {dist(a,b,0),dist(a,b,1)};
}
void _(){
cin >> n >> k >> q >> t;
for(int i=1;i<=n;i++) cin >> par[i][0];
for(int i=1;i<=n;i++) cin >> par[i][1];
for(int i=1;i<=n;i++){
if(par[i][0]==-1) r[0]=i;
else{
lift[i][0][0]=par[i][0];
v[par[i][0]][0].push_back(i);
v[i][0].push_back(par[i][0]);
}
}
for(int i=1;i<=n;i++){
if(par[i][1]==-1) r[1]=i;
else{
lift[i][0][1]=par[i][1];
v[par[i][1]][1].push_back(i);
v[i][1].push_back(par[i][1]);
}
}
for(int u=0;u<2;u++){
ti=0;
dfs(r[u],u);
}
vector<int> sec;
vector<array<int,3>> ask;
for(int i=1;i<=k;i++) sec.push_back(i);
for(int u=0;u<2;u++){
vector<int> virt;
for(int i=1;i<=k;i++) virt.push_back(i);
sort(all(virt),[&](int a,int b){
return tin[a][u]<tin[b][u];
});
for(int i=1;i<k;i++) virt.push_back(lca(virt[i-1],virt[i],u));
sort(all(virt),[&](int a,int b){
return tin[a][u]<tin[b][u];
});
virt.erase(unique(all(virt)),virt.end());
R[u]=virt[0];
stack<int> s;
for(int x:virt){
while(!s.empty() && !is_anc(s.top(),x,u)) s.pop();
if(!s.empty()){
ask.push_back({s.top(),x,u});
up[x][0][u]=s.top();
g[s.top()][u].push_back(x);
}
s.push(x);
}
ti=0;
dfs2(R[u],u);
}
for(int x:sec) cout << x << ' ';
cout << endl;
for(auto x:ask){
cout << "? " << x[0] << ' ' << x[1] << endl;
}
cout << '!' << endl;
for(int i=0;i<sz(ask);i++){
int a = ask[i][0] , b = ask[i][1] , u = ask[i][2];
int res[4];
cin >> res[0] >> res[1] >> res[2] >> res[3];
if(u==0) depth[b][u]=depth[a][u]+res[1];
else depth[b][u]=depth[a][u]+res[3];
}
vector<array<int,2>> U;
for(int i=1;i<=t;i++){
int a,b;
cin >> a >> b;
U.push_back({a,b});
}
for(auto S:U){
int a = S[0] , b = S[1];
auto ANS = Answer(a,b);
cout << ANS[0] << ' ' << ANS[1] << endl;
}
}
int32_t main(){
//cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
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... |