#include "bits/stdc++.h"
using namespace std;
#define int long long
#ifdef LOCAL
#include "debug.cpp"
#else
#define debug(...)
#endif
int n,k;
int bit[2][1300015];
void add(int e,int v,int ty){
while(e<=n){
bit[ty][e]+=v;
e+=e&-e;
}
}
int sum(int e,int ty){
int su = 0;
while(e>=1){
su+=bit[ty][e];
e-=e&-e;
}
return su;
}
vector<pair<int,int>> queries;
vector<int> v1,st1,v2,st2;set<int> loli,loli2;
int in[1300001][2],outt[1300001][2],timer = 0;
int P[1300001][2][20];
int PR[1300001][2][20],cost[1300001][2][20];
int DEP[1300001][2];
int dep[1300001][2];
int root[1300001][2],vis[1300001][2];
vector<int> adj[2][1300001],vert[1300001][2];
vector<pair<int,int>> lens[1300001][2],computed[1300001][2];
void dfs(int i,int pr,int ty){
if(ty){
if(v1.size()<k)v1.push_back(i);
if(v2.size()<k)v2.push_back(i);
}
in[i][ty] = ++timer;
P[i][ty][0] = pr;
dep[i][ty] = dep[pr][ty]+1;
for(int j = 1;j<20;j++){
P[i][ty][j] = P[P[i][ty][j-1]][ty][j-1];
}
for(auto j:adj[ty][i]){
if(j==pr)continue;
dfs(j,i,ty);
}
outt[i][ty] = timer;
}
bool comp1(int a,int b){
return in[a][0]<in[b][0];
}
bool comp2(int a,int b){
return in[a][1]<in[b][1];
}
int lca(int a,int b,int ty){
if(dep[a][ty]<dep[b][ty])swap(a,b);
for(int i = 19;i>=0;i--){
if(dep[a][ty]-(1<<i)>=dep[b][ty]){
a = P[a][ty][i];
}
}
if(a==b)return a;
for(int i = 19;i>=0;i--){
if(P[a][ty][i]!=P[b][ty][i]){
a = P[a][ty][i];
b = P[b][ty][i];
}
}
return P[a][ty][0];
}
bool upper(int a,int b,int ty){
return in[a][ty]<=in[b][ty]&&outt[a][ty]>=outt[b][ty];
}
void dfs3(int i,int pr,int cost,int ty){
root[i][ty] = cost;
vis[i][ty] = 1;
for(auto j:lens[i][ty]){
if(!vis[j.first][ty]){
dfs3(j.first,i,cost+j.second,ty);
}
}
}
void dfs2(int i,int pr,int ty){
PR[i][ty][0] = pr;
cost[i][ty][0] = root[i][ty]-root[pr][ty];
DEP[i][ty] = DEP[pr][ty]+1;
for(int j = 1;j<20;j++){
PR[i][ty][j] = PR[PR[i][ty][j-1]][ty][j-1];
cost[i][ty][j] = cost[i][ty][j-1]+cost[PR[i][ty][j-1]][ty][j-1];
}
for(auto j:vert[i][ty]){
if(j==pr)continue;
dfs2(j,i,ty);
}
}
int lca2(int a,int b,int ty){
if(DEP[a][ty]<DEP[b][ty])swap(a,b);
int summ = 0;
for(int i = 19;i>=0;i--){
if(DEP[a][ty]-(1<<i)>=DEP[b][ty]){
summ+=cost[a][ty][i];
a = PR[a][ty][i];
}
}
if(a==b)return summ;
for(int i = 19;i>=0;i--){
if(PR[a][ty][i]!=PR[b][ty][i]){
summ+=cost[a][ty][i];
summ+=cost[b][ty][i];
a = PR[a][ty][i];
b = PR[b][ty][i];
}
}
return summ+cost[a][ty][0]+cost[b][ty][0];
}
void query(int a,int b){
cout<<"? "<<a<<" "<<b<<endl;
//int x,y,z,e;
//cin>>x>>y>>z>>e;
//return {x,y,z,e};
}
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);
//freopen("prize.in.1c","r",stdin);
int g,t;
cin>>n>>k>>g>>t;
int root1 , root2;
for(int i = 1;i<=n;i++){
int x;cin>>x;
if(x==-1){
root1 = i;
}else{
adj[0][x].push_back(i);
adj[0][i].push_back(x);
}
}
for(int i = 1;i<=n;i++){
int x;cin>>x;
if(x==-1){
root2 = i;
}else{
adj[1][x].push_back(i);
adj[1][i].push_back(x);
}
}
dfs(root1,0,0);
timer = 0;
dfs(root2,0,1);
for(auto i:v1){
cout<<i<<" ";
}
cout<<endl;
sort(v1.begin(),v1.end(),comp1);
sort(v2.begin(),v2.end(),comp1);
for(int i = 1;i<k;i++){
query(v1[i-1],v1[i]);
//lens[lca(v[i],v[i-1],0)].push_back({v[i-1],lol[0]});
//lens[lca(v[i],v[i-1],0)].push_back({v[i],lol[1]});
v1.push_back(lca(v1[i],v1[i-1],0));
}
for(int i = 1;i<k;i++){
//query(v2[i-1],v2[i]);
//lens[lca(v[i],v[i-1],0)].push_back({v[i-1],lol[0]});
//lens[lca(v[i],v[i-1],0)].push_back({v[i],lol[1]});
v2.push_back(lca(v2[i],v2[i-1],1));
}
cout<<"!"<<endl;
for(int i = 1;i<k;i++){
int x,y,z,e;cin>>x>>y>>z>>e;
lens[lca(v1[i],v1[i-1],0)][0].push_back({v1[i-1],x});
lens[lca(v1[i],v1[i-1],0)][0].push_back({v1[i],y});
lens[v1[i-1]][0].push_back({lca(v1[i],v1[i-1],0),-x});
lens[v1[i]][0].push_back({lca(v1[i],v1[i-1],0),-y});
lens[lca(v2[i],v2[i-1],1)][1].push_back({v2[i-1],z});
lens[lca(v2[i],v2[i-1],1)][1].push_back({v2[i],e});
lens[v2[i-1]][1].push_back({lca(v2[i],v2[i-1],1),-z});
lens[v2[i]][1].push_back({lca(v2[i],v2[i-1],1),-e});
}
sort(v1.begin(),v1.end(),comp1);
for(auto i:v1)loli.insert(i);
v1.clear();
for(auto i:loli)v1.push_back(i);
sort(v1.begin(),v1.end(),comp1);
st1.push_back(v1[0]);
for(int i = 1;i<v1.size();i++){
while(st1.size()>1&&!upper(st1.back(),v1[i],0)){
vert[st1[st1.size()-2]][0].push_back(st1.back());
st1.pop_back();
}
st1.push_back(v1[i]);
}
while(st1.size()>1){
vert[st1[st1.size()-2]][0].push_back(st1.back());
st1.pop_back();
}
sort(v2.begin(),v2.end(),comp2);
for(auto i:v2)loli2.insert(i);
v2.clear();
for(auto i:loli2)v2.push_back(i);
sort(v2.begin(),v2.end(),comp2);
st2.push_back(v2[0]);
for(int i = 1;i<v2.size();i++){
while(st2.size()>1&&!upper(st2.back(),v2[i],1)){
vert[st2[st2.size()-2]][1].push_back(st2.back());
st2.pop_back();
}
st2.push_back(v2[i]);
}
while(st2.size()>1){
vert[st2[st2.size()-2]][1].push_back(st2.back());
st2.pop_back();
}
timer = 0;
dfs3(st1[0],0,0,0);
dfs3(st2[0],0,0,1);
dfs2(st1[0],0,0);
dfs2(st2[0],0,1);
while(t--){
int a,b;cin>>a>>b;
queries.push_back({a,b});
}
for(auto i:queries){
int a = i.first , b = i.second;
cout<<lca2(a,b,0)<<" "<<lca2(a,b,1)<<endl;
}
}
Compilation message
Main.cpp: In function 'void dfs(long long int, long long int, long long int)':
Main.cpp:38:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
38 | if(v1.size()<k)v1.push_back(i);
| ~~~~~~~~~^~
Main.cpp:39:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
39 | if(v2.size()<k)v2.push_back(i);
| ~~~~~~~~~^~
Main.cpp: In function 'int main()':
Main.cpp:189:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
189 | for(int i = 1;i<v1.size();i++){
| ~^~~~~~~~~~
Main.cpp:206:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
206 | for(int i = 1;i<v2.size();i++){
| ~^~~~~~~~~~
Main.cpp:150:8: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
150 | dfs(root1,0,0);
| ~~~^~~~~~~~~~~
Main.cpp:152:8: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
152 | dfs(root2,0,1);
| ~~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1980 ms |
808236 KB |
Output is correct |
2 |
Correct |
2230 ms |
846600 KB |
Output is correct |
3 |
Correct |
1446 ms |
788456 KB |
Output is correct |
4 |
Correct |
1433 ms |
780276 KB |
Output is correct |
5 |
Correct |
1599 ms |
815056 KB |
Output is correct |
6 |
Correct |
1928 ms |
806984 KB |
Output is correct |
7 |
Correct |
1856 ms |
806804 KB |
Output is correct |
8 |
Correct |
1807 ms |
797520 KB |
Output is correct |
9 |
Correct |
1465 ms |
786720 KB |
Output is correct |
10 |
Correct |
1497 ms |
808432 KB |
Output is correct |
11 |
Correct |
1360 ms |
760424 KB |
Output is correct |
12 |
Correct |
1513 ms |
804328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2265 ms |
843652 KB |
Output is correct |
2 |
Correct |
1966 ms |
777204 KB |
Output is correct |
3 |
Correct |
1539 ms |
813892 KB |
Output is correct |
4 |
Correct |
1707 ms |
832584 KB |
Output is correct |
5 |
Correct |
1581 ms |
821568 KB |
Output is correct |
6 |
Correct |
1957 ms |
805516 KB |
Output is correct |
7 |
Correct |
2220 ms |
834228 KB |
Output is correct |
8 |
Correct |
2245 ms |
837044 KB |
Output is correct |
9 |
Correct |
2141 ms |
839096 KB |
Output is correct |
10 |
Correct |
2146 ms |
844136 KB |
Output is correct |
11 |
Correct |
1832 ms |
813132 KB |
Output is correct |
12 |
Correct |
2103 ms |
841912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1179 ms |
499432 KB |
Output is correct |
2 |
Correct |
1170 ms |
498640 KB |
Output is correct |
3 |
Correct |
904 ms |
477256 KB |
Output is correct |
4 |
Correct |
961 ms |
507664 KB |
Output is correct |
5 |
Correct |
871 ms |
482272 KB |
Output is correct |
6 |
Correct |
1010 ms |
481976 KB |
Output is correct |
7 |
Correct |
1060 ms |
482836 KB |
Output is correct |
8 |
Correct |
1047 ms |
482064 KB |
Output is correct |
9 |
Correct |
925 ms |
482852 KB |
Output is correct |
10 |
Correct |
959 ms |
482400 KB |
Output is correct |
11 |
Correct |
982 ms |
482768 KB |
Output is correct |
12 |
Correct |
934 ms |
482004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2798 ms |
756132 KB |
Output is correct |
2 |
Correct |
2875 ms |
755656 KB |
Output is correct |
3 |
Correct |
1923 ms |
715948 KB |
Output is correct |
4 |
Correct |
1905 ms |
714832 KB |
Output is correct |
5 |
Correct |
2003 ms |
715744 KB |
Output is correct |
6 |
Correct |
2594 ms |
727612 KB |
Output is correct |
7 |
Correct |
2603 ms |
726568 KB |
Output is correct |
8 |
Correct |
2688 ms |
726696 KB |
Output is correct |
9 |
Correct |
2371 ms |
725572 KB |
Output is correct |
10 |
Correct |
2394 ms |
725860 KB |
Output is correct |
11 |
Correct |
2482 ms |
725900 KB |
Output is correct |
12 |
Correct |
2438 ms |
725848 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
3332 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |