#include<bits/stdc++.h>
using namespace std;
#define pb push_back
using pii=pair<int,int>;
const int lim=1e6+100;
int n,k,q,t;
vector<int>v[lim],u[lim];
int par1[lim],par2[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;
void edfs(int node){
tin1[node]=tt++;
for(int j:v[node]){
par1[j]=node;
edfs(j);
}
tout1[node]=tt-1;
}
unordered_set<int>dudes;
void cdfs(int node){
if(dudes.size()==k)return;
dudes.insert(node);
if(dudes.size()==k)return;
for(int j:v[node]){
cdfs(j);
}
}
vector<int>order;
void odfs(int node){
tin2[node]=tt++;
if(dudes.count(node)){
order.pb(node);
}
for(int j:u[node]){
par2[j]=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];
}
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];
}
return lift2[x][0];
}
void ldfs1(int node){
for(int i=1;i<=23;i++)
lift1[node][i]=lift1[lift1[node][i-1]][i-1];
for(int j:v[node])ldfs1(j);
}
void ldfs2(int node){
for(int i=1;i<=23;i++)
lift2[node][i]=lift2[lift2[node][i-1]][i-1];
for(int j:u[node])ldfs2(j);
}
int main(){
cin>>n>>k>>q>>t;
int root1,root2;
for(int i=1;i<=n;i++){
int p;
cin>>p;
if(p==-1)root1=i;
else v[p].pb(i);
}
for(int i=1;i<=n;i++){
int p;
cin>>p;
if(p==-1)root2=i;
else u[p].pb(i);
}
tin1[0]=tin2[0]=INT_MIN;
tout1[0]=tout2[0]=INT_MAX;
tt=1;
edfs(root1);
cdfs(root1);
for(int i:dudes)cout<<i<<' ';
cout<<endl;
cout.flush();
tt=1;
odfs(root2);
for(int i=1;i<=n;i++){
lift1[i][0]=par1[i];
lift2[i][0]=par2[i];
}
ldfs1(root1);
ldfs2(root2);
for(int i=0;i+1<order.size();i++){
cout<<"? "<<order[i]<<' '<<order[i+1]<<endl;
}
cout<<"!";
cout<<endl;
cout.flush();
dep1[order[0]]=dep2[order[0]]=0;
for(int i=0;i+1<order.size();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]<<endl;
}
cout.flush();
}
Compilation message
Main.cpp: In function 'void cdfs(int)':
Main.cpp:29:18: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
29 | if(dudes.size()==k)return;
| ~~~~~~~~~~~~^~~
Main.cpp:31:18: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
31 | if(dudes.size()==k)return;
| ~~~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i=0;i+1<order.size();i++){
| ~~~^~~~~~~~~~~~~
Main.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int i=0;i+1<order.size();i++){
| ~~~^~~~~~~~~~~~~
Main.cpp:111:8: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
111 | ldfs1(root1);
| ~~~~~^~~~~~~
Main.cpp:112:8: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
112 | ldfs2(root2);
| ~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1448 ms |
219936 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1364 ms |
220652 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1238 ms |
215440 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2778 ms |
383864 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2928 ms |
389092 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
