QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #775563 | #9570. Binary Tree | WaO_o | WA | 3ms | 7736kb | C++20 | 10.0kb | 2024-11-23 16:13:15 | 2024-11-23 16:13:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define deg( x ) cout<<""#x"="<<x<<endl
//#define endl '\n'
#define pll pair<int,int>
#define fr first
#define se second
const int N=1e5+10;
vector<int> G[ N ];
int faa[ N ];
map< int , int > mp;
void init( int n ){
for( int i=1; i<=n; i++ ){
G[ i ].clear();
faa[ i ]=0;
}
mp.clear();
}
int len=0;
int bt;
bool is( int u , int v ){
if( u > v ) swap( u , v );
return mp[ ( u<<25ll )|v ]==1;
}
void del( int u , int v ){
if( u > v ) swap( u , v );
mp[ ( u<<25ll )|v ]=1;
}
void dfs( int rt , int fa , int now ){
faa[ rt ]=fa;
if( now > len ){
len=now;
bt=rt;
}
for( auto son:G[ rt ] ){
if( son==fa || is( rt , son ) ) continue;
dfs( son , rt , now+1 );
}
}
int get( int a , int b ){
cout<<"? "<<a<<" "<<b<<endl;
int re;
cin>>re;
if( re==0 ){
int num=len+1;
num/=2;
int o=b;
for( int i=1; i<num; i++ ){
o=faa[ o ];
}
del( o , faa[ o ] );
return a;
}
else if( re==1 ){
int num=len/2;
int o=b;
for( int i=1; i<num; i++ ){
o=faa[ o ];
//deg( o );
}
del( o , faa[ o ] );
o=faa[ o ];
del( o , faa[ o ] );
return o;
}
else{
int num=len/2;
int o=b;
for( int i=1; i<num; i++ ){
o=faa[ o ];
}
//cout<<o<<"->"<<faa[ o ]<<endl;
del( o , faa[ o ] );
return b;
}
}
void ddfs( int rt , int fa , int num , int b , int &o ){
if( rt==b ){
o=num;
return ;
}
for( auto son:G[ rt ] ){
if( son==fa || is( son , rt ) ) continue;
ddfs( son , rt , num+1 , b , o );
}
}
int hhget( int a , int b , int ans ){
int aa=-1;
ddfs( ans , 0 , 0 , a , aa );
int bb=-1;
ddfs( ans , 0 , 0 , b , bb );
if( aa<0 || bb<0 ) cout<<"wfdd"<<endl;
int re;
if( aa==bb ) re=1;
else if( aa < bb ) re=0;
else re=2;
if( re==0 ){
int num=len+1;
num/=2;
int o=b;
for( int i=1; i<num; i++ ){
o=faa[ o ];
}
del( o , faa[ o ] );
return a;
}
else if( re==1 ){
int num=len/2;
int o=b;
for( int i=1; i<num; i++ ){
o=faa[ o ];
}
del( o , faa[ o ] );
o=faa[ o ];
del( o , faa[ o ] );
return o;
}
else{
int num=len/2;
int o=b;
for( int i=1; i<num; i++ ){
o=faa[ o ];
}
//cout<<o<<"->"<<faa[ o ]<<endl;
del( o , faa[ o ] );
return b;
}
}
int hhwen( int a , int b , int ans ){
int re;
int aa=-1;
ddfs( ans , 0 , 0 , a , aa );
int bb=-1;
ddfs( ans , 0 , 0 , b , bb );
if( aa<0 || bb<0 ) cout<<"wfdd"<<endl;
if( aa==bb ) re=1;
else if( aa < bb ) re=0;
else re=2;
return re;
}
pll ma[ N ];
void odfs( int rt , int fa ){
pll te={ -1 , rt };
for( auto son:G[ rt ] ){
if( fa==son || is( rt , son ) ) continue;
odfs( son , rt );
if( ma[ son ].fr > te.fr ){
te=ma[ son ];
}
}
ma[ rt ]={ te.fr+1 , te.se };
}
int wen( int a , int b ){
int re;
cout<<"? "<<a<<" "<<b<<endl;
cin>>re;
return re;
}
pll A[ N ];
void hh( int n ){
for( int i=1; i<=n; i++ ){
mp.clear();
int ans=i;
int cnt=0;
int st=1;
while( 1 ){
int a,b;
len=0;
dfs( st , 0 , 1 );
if( len==1 ){
//cout<<"! "<<st<<endl;
break;
}
a=bt;
len=0;
dfs( a , 0 , 1 );
b=bt;
int o=b;
int num=( len+1 )/2;
for( int i=1; i<num; i++ ){
o=faa[ o ];
}
odfs( o , 0 );
int cnt=0;
for( auto son:G[ o ] ){
if( is( son , o ) ) continue;
cnt++;
A[ cnt ]={ ma[ son ].fr , son };
}
sort( A+1 , A+1+cnt );
int re=0;
if( cnt == 3 ){
if( A[ 1 ].fr == A[ 2 ].fr ){
cnt++;
re=hhwen( ma[ A[ 1 ].se ].se , ma[ A[ 2 ].se ].se , ans );
if( re == 0 ){
del( A[ 2 ].se , o );
del( A[ 3 ].se , o );
}
else if( re==1 ){
del( A[ 2 ].se , o );
del( A[ 1 ].se , o );
}
else{
del( A[ 1 ].se , o );
del( A[ 3 ].se , o );
}
st=o;
}
else if( A[ 2 ].fr == A[ 3 ].fr ){
cnt++;
re=hhwen( ma[ A[ 2 ].se ].se , ma[ A[ 3 ].se ].se , ans );
if( re == 0 ){
del( A[ 1 ].se , o );
del( A[ 3 ].se , o );
}
else if( re==1 ){
del( A[ 2 ].se , o );
del( A[ 3 ].se , o );
}
else{
del( A[ 2 ].se , o );
del( A[ 1 ].se , o );
}
st=o;
}
else{
cnt++;
re=hhwen( ma[ A[ 3 ].se ].se , ma[ A[ 2 ].se ].se , ans );
if( re==0 ){
st=o;
del( o , A[ 2 ].se );
del( o , A[ 1 ].se );
}
else if( re==2 ){
del( A[ 3 ].se , o );
a=ma[ A[ 2 ].se ].se;
b=ma[ A[ 1 ].se ].se;
cnt++;
st=hhget( a , b , ans );
}
}
}
else{
cnt++;
st=hhget( a , b , ans );
}
}
int uu=log2( n );
if( cnt>uu ){
cout<<"gg"<<endl;
}
else if( ans!=st ){
cout<<"wa"<<endl;
}
else{
cout<<cnt<<" ac "<<ans<<endl;
}
}
}
void solve(){
int n;
cin>>n;
init( n );
for( int i=1,u,v; i<=n; i++ ){
cin>>u>>v;
if( u!=0 ){
G[ i ].emplace_back( u );
G[ u ].emplace_back( i );
}
swap( u ,v );
if( u!=0 ){
G[ i ].emplace_back( u );
G[ u ].emplace_back( i );
}
}
//hh( n );
int st=1;
while( 1 ){
int a,b;
len=0;
dfs( st , 0 , 1 );
if( len==1 ){
cout<<"! "<<st<<endl;
break;
}
a=bt;
len=0;
dfs( a , 0 , 1 );
b=bt;
int o=b;
int num=( len+1 )/2;
for( int i=1; i<num; i++ ){
o=faa[ o ];
}
odfs( o , 0 );
int cnt=0;
for( auto son:G[ o ] ){
if( is( son , o ) ) continue;
cnt++;
A[ cnt ]={ ma[ son ].fr , son };
}
sort( A+1 , A+1+cnt );
int re=0;
// cout<<a<<"->"<<b<<endl;
// deg( cnt );
// deg( o );
if( cnt == 3 ){
if( A[ 1 ].fr == A[ 2 ].fr ){
re=wen( ma[ A[ 1 ].se ].se , ma[ A[ 2 ].se ].se );
if( re == 0 ){
del( A[ 2 ].se , o );
del( A[ 3 ].se , o );
}
else if( re==1 ){
del( A[ 2 ].se , o );
del( A[ 1 ].se , o );
}
else{
del( A[ 1 ].se , o );
del( A[ 3 ].se , o );
}
st=o;
}
else if( A[ 2 ].fr == A[ 3 ].fr ){
re=wen( ma[ A[ 2 ].se ].se , ma[ A[ 3 ].se ].se );
if( re == 0 ){
del( A[ 1 ].se , o );
del( A[ 3 ].se , o );
}
else if( re==1 ){
del( A[ 2 ].se , o );
del( A[ 3 ].se , o );
}
else{
del( A[ 2 ].se , o );
del( A[ 1 ].se , o );
}
st=o;
}
else{
re=wen( ma[ A[ 3 ].se ].se , ma[ A[ 2 ].se ].se );
if( re==0 ){
st=o;
del( o , A[ 2 ].se );
del( o , A[ 1 ].se );
}
else if( re==2 ){
del( A[ 3 ].se , o );
a=ma[ A[ 2 ].se ].se;
b=ma[ A[ 1 ].se ].se;
st=a;
len=0;
dfs( st , 0 , 1 );
if( len==1 ){
cout<<"! "<<st<<endl;
break;
}
a=bt;
len=0;
dfs( a , 0 , 1 );
b=bt;
st=get( a , b );
}
}
}
else{
st=get( a , b );
}
}
}
signed main() {
ios::sync_with_stdio( 0 );
cin.tie( 0 ); cout.tie( 0 );
int T=1;
cin>>T;
while( T-- ){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5752kb
input:
2 5 0 0 1 5 2 4 0 0 0 0 1 1 2 0 2 0 0 2
output:
? 1 5 ? 4 2 ! 3 ? 2 1 ! 1
result:
ok OK (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 7736kb
input:
5555 8 2 0 8 6 0 0 3 0 0 0 7 0 0 0 5 4 2 0 2 8 0 0 1 4 2 0 0 0 7 8 0 0 3 0 6 0 2 1 0 8 5 8 0 0 1 7 0 0 0 0 4 2 0 0 6 0 2 0 0 5 4 5 3 1 0 0 0 0 0 0 1 0 8 0 0 0 0 5 6 0 0 1 4 2 0 3 8 0 0 1 0 5 3 0 5 1 0 0 0 0 4 0 2 2 5 5 0 0 0 0 0 3 0 2 4 1 2 3 3 0 1 0 0 0 2 2 2 0 0 0 2 3 2 3 0 0 0 0 0 10 2 8 9 7 0 0 ...
output:
? 3 7 ? 1 7 ? 2 1 ! 1 ? 6 1 ? 1 3 ? 4 2 ! 4 ? 4 7 ? 5 7 ? 1 5 ! 1 ? 4 5 ? 3 1 ! 3 ? 1 2 ? 8 3 ! 8 ? 4 3 ? 1 3 ! 3 ? 1 2 ? 3 5 ! 5 ? 3 2 ! 2 ? 2 1 ! 1 ? 2 3 ! 2 ? 8 10 ? 2 5 ? 3 4 ? 7 6
result:
wrong answer Too many queries (test case 11)