Can anyone tell me any logical error, or implementation error in this code.
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
int query1(int x){
int ans;
cout<<"1 "<<x<<endl;
cin>>ans;
return ans;
}
int query2(int x, int y){
int ans;
cout<<"2 "<<x<<" "<<y<<endl;
cin>>ans;
return ans;
}
int solve(){
int x=1,y;
cin>>y;
while(y!=0){
x=query2(x,y);
y=query1(x);
}
return x;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t,x;
cin >>t;
//precompute();
while(t--){
//init();
cout<<"3 "<<solve()<<endl;
cin>>x;
}
}
Goodbye my rating.
Everything is correct but you missed one thing. In worst case your code will use 2h+2 queries. if you get y=2 break and use query2 only for that bcz for a leaf node there can be only one node with distance 2
2 Likes
I ran the loop h times because at every iteration, the height decreases by one. I believe that there might be a chance that you may be exceeding the query limit because you are asking for a fail query before exiting.
1 Like
This costed me a WA too, I’m not sure why is this a case, but one of your queries is redundant, you can exit out of your while loop when y becomes 2 and the node which you will get upon asking the query2 will be the special node. So there is no need to do query1 again. I changed this in my code and got an AC.
1 Like
Because at each step you reject at least half of the remaining leaves. Hence it needs exactly 2h+1 queries to find the dist=2 node. And hence asking one more will give WA.
2 Likes
after 27th line, add if(n==2) break;
1 Like
I will throw 
on you @coronavirus42 XD
2 Likes
Yeah I am filling a bucket with sanitizer. Will put my laptop inside the bucket soon XD
2 Likes
