ABC019 D問題 高橋くんと木の直径

多分自分初めてリアクティブ形式の問題やりました。すごいデバッグしづらい…。

問題は、50個以内の頂点がある木(辺はわからない)を与えられるので、100回以内の質問(こことここの長さは？)で木の直径を出力せよ、という問題。

いや木の直径の求め方なんて知らねぇよ…。
ある頂点から最長距離の頂点vを求めて、そのvからの最長距離が木の直径らしいです(証明は簡単)。

思ったんですが、こういう知らないけど調べたらすぐ出てきそうなものって、コンテスト中に調べるのも大事ですね(できないコンテストも多いけど)。

    int N;
    cin >> N;
    rep(i, 51) rep(j, 51){
        G[i][j] = (i == j ? 0 : INF);
    }
    int index = -1;
    int res = 0;
    for(int i=2; i<=N; i++){
        cout << "? " << 1 << " " << i << endl;
        int dist; cin >> dist;
        if(dist > res){
            res = dist;
            index = i;
        }
    }
    for(int i=1; i<=N; i++){
        if(index == i) continue;
        cout << "? " << index << " " << i << endl;
        int dist; cin >> dist;
        res = max(res, dist);
    }
    cout << "! " << res << endl;