CF-967-div2-C. Guess The Tree · znzryb

## AC代码

加了一段这个`// 两个点都已经已知，就不需要继续找了`

然后找的次数少了，就AC了。

```cpp
if(vis[a] && vis[b])    // 两个点都已经已知，就不需要继续找了
        return;
```

[](https://codeforces.com/contest/2001/submission/291568701)

```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e3)+10;
ll n,T;
bitset<N> vis;
bool ans[N][N];


void solve(ll a,ll b) {
    if(ans[a][b])
        return;
    if(vis[a] && vis[b])    // 两个点都已经已知，就不需要继续找了
        return;
    cout<<"? "<<a<<" "<<b<<endl;
    ll ret;
    cin>>ret;
    if(ret<0)   // 如果读入-1 需立即终止程
        exit(0);
    if(ret==a) {
        vis[a]=true,vis[b]=true;
        ans[a][b]=true;
    }else {
        solve(a,ret);
        solve(ret,b);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        cin>>n;
        vis.reset();
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                ans[i][j]=false;
        for(int i=2;i<=n;++i) {
            if(vis[i])
                continue;
            solve(1,i);
        }
        cout<<"! ";
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=n;++j) {
                if(ans[i][j])
                    cout<<i<<" "<<j<<" ";
            }
        }
        cout<<endl;
    }
}
// WA on test 5 https://codeforces.com/contest/2001/submission/291518387
// AC https://codeforces.com/contest/2001/submission/291568701
```

## 心路历程（WA，TLE，MLE……）

WA on test 5 

[](https://codeforces.com/contest/2001/submission/291518387)

 **Probably, the solution is executed with error 'out of bounds' on the line 24**

我也不太理解为什么会越界数组，除非他给我输入-1

![image](https://media.znzryb.com/20241112-53b93a11/image_a8bc2efb.png)

好像还真是。

```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e3)+10;
ll n,T;
bitset<N> vis;
bool ans[N][N];


void solve(ll a,ll b) {
    if(ans[a][b])
        return;
    cout<<"? "<<a<<" "<<b<<endl;
    ll ret;
    cin>>ret;
    if(ret==a) {
        vis[a]=true,vis[b]=true;
        ans[a][b]=true;
    }else {
        solve(a,ret);
        solve(ret,b);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        cin>>n;
        vis.reset();
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                ans[i][j]=false;
        for(int i=2;i<=n;++i) {
            if(vis[i])
                continue;
            solve(1,i);
        }
        cout<<"! ";
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=n;++j) {
                if(ans[i][j])
                    cout<<i<<" "<<j<<" ";
            }
        }
        cout<<endl;
    }
}
// WA on test 5 https://codeforces.com/contest/2001/submission/291518387
```