#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
using pii=pair<int,int>;
const int lim=1e6+100;
int n,k,q,t;
vector<int>v[lim],u[lim];
int lift1[lim][25],lift2[lim][25];
int tin1[lim],tin2[lim],tout1[lim],tout2[lim];
int dep1[lim],dep2[lim];
int tt=1;
unordered_set<int>dudes;
void edfs(int node){
for(int i=1;i<=23;i++)
lift1[node][i]=lift1[lift1[node][i-1]][i-1];
tin1[node]=tt++;
if(dudes.size()<k)dudes.insert(node);
for(int j:v[node]){
lift1[j][0]=node;
edfs(j);
}
tout1[node]=tt-1;
}
vector<int>order;
void odfs(int node){
for(int i=1;i<=23;i++)
lift2[node][i]=lift2[lift2[node][i-1]][i-1];
tin2[node]=tt++;
if(dudes.count(node)){
order.pb(node);
}
for(int j:u[node]){
lift2[j][0]=node;
odfs(j);
}
tout2[node]=tt-1;
}
#define ispar1(x,y) (tin1[x]<=tin1[y]&&tout1[y]<=tout1[x])
#define ispar2(x,y) (tin2[x]<=tin2[y]&&tout2[y]<=tout2[x])
int lca1(int x,int y){
if(ispar1(x,y))return x;
if(ispar1(y,x))return y;
for(int i=23;0<=i;i--){
if(lift1[x][i]&&!ispar1(lift1[x][i],y))x=lift1[x][i];
}
assert(ispar1(lift1[x][0],y)&&!ispar1(x,y));
return lift1[x][0];
}
int lca2(int x,int y){
if(ispar2(x,y))return x;
if(ispar2(y,x))return y;
for(int i=23;0<=i;i--){
if(lift2[x][i]&&!ispar2(lift2[x][i],y))x=lift2[x][i];
}
assert(ispar2(lift2[x][0],y)&&!ispar2(x,y));
return lift2[x][0];
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie();
cin>>n>>k>>q>>t;
int root1,root2;
for(int i=1;i<=n;i++){
cin>>lift1[i][0];
if(lift1[i][0]==-1)root1=i,lift1[i][0]++;
else v[lift1[i][0]].pb(i);
}
for(int i=1;i<=n;i++){
cin>>lift2[i][0];
if(lift2[i][0]==-1)root2=i,lift2[i][0]++;
else u[lift2[i][0]].pb(i);
}
tt=1;
edfs(root1);
odfs(root2);
for(int i=0;i<k;i++){
cout<<order[i];
if(i==k-1)cout<<endl;
else cout<<' ';
}
for(int i=0;i+1<k;i++){
cout<<"? "<<order[i]<<' '<<order[i+1]<<'\n';
}
cout<<"!"<<endl;
dep1[order[0]]=dep2[order[0]]=0;
for(int i=0;i+1<k;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
int l1=lca1(order[i],order[i+1]);
int l2=lca2(order[i],order[i+1]);
dep1[l1]=dep1[order[i]]-a;
dep2[l2]=dep2[order[i]]-c;
dep1[order[i+1]]=dep1[l1]+b;
dep2[order[i+1]]=dep2[l2]+d;
}
for(int i=0;i<t;i++){
int x,y;
cin>>x>>y;
int l1=lca1(x,y);
int l2=lca2(x,y);
cout<<dep1[x]+dep1[y]-2*dep1[l1]<<' '<<dep2[x]+dep2[y]-2*dep2[l2]<<'\n';
}
//assert(0);
cout.flush();
}
Compilation message
Main.cpp: In function 'void edfs(long long int)':
Main.cpp:23:18: warning: comparison of integer expressions of different signedness: 'std::unordered_set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
23 | if(dudes.size()<k)dudes.insert(node);
| ~~~~~~~~~~~~^~
Main.cpp: In function 'int main()':
Main.cpp:83:7: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
83 | edfs(root1);
| ~~~~^~~~~~~
Main.cpp:84:7: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
84 | odfs(root2);
| ~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
829 ms |
356736 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
880 ms |
358952 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
821 ms |
353016 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2033 ms |
619144 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1969 ms |
632696 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
