提出 #32613941

---

ソースコード 拡げる

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>

static inline int query(int u, int v) {
    int answer;

    std::cout << "? " << u << " " << v << std::endl;
    std::cin >> answer;
    if (answer == -1) std::exit(0);

    return answer;
}

int main() {
    int n, queryAnswer, result;

    // descendants[i] := list of descendants of the vertex 1 (the root) at depth i
    // That is, descendants[1] is the list of direct children of 1
    std::vector<int> descendants[3];

    std::cin >> n;

    for (int i = 3; i <= n; i++) {
        queryAnswer = query(1, i);
        if (queryAnswer < 3) descendants[queryAnswer].push_back(i);

        if (descendants[1].size() == 2) break; // two children of 1 are enough to find the depth of 2
    }

    if (descendants[1].empty()) {
        // 2 must be a direct child of 1, if 1 has no other children
        result = 1;
    }
    else if (descendants[1].size() == 1) {
        queryAnswer = query(descendants[1].front(), 2);

        if (queryAnswer == 2) { // 2 is either a direct child of 1 or a descendant of descendants[1].front()
            result = 1; // let us assume that 2 is a direct child of 1

            for (int i : descendants[2]) {
                // i is either a child of descendants[1].front(), or a child of 2 (if 2 is a child of 1)

                if (query(i, 2) == 1) { // We found i that is either a child or a parent of 2
                    // If i is a child of descendants[1].front(), then 2 is a child of i
                    // Otherwise, i is a child of 2

                    result = query(i, descendants[1].front()) == 1 ? 3 : 1;
                    break;
                }
            }
        }
        else { // 2 must be a descendant of descendants[1].front() (the only direct child of 1)
            result = queryAnswer + 1;
        }
    }
    else { // descendants[1].size() == 2
        // 2 may be a descendant of descendants[1][0], descendants[1][1], or of neither of them
        // If 2 is a descendant of descendants[1][i], then query(descendants[1][i], 2) = d(1, 2) - 1
        // If 2 is NOT a descendant of descendants[1][i], then query(descendants[1][i], 2) = d(1, 2) + 1
        
        result = std::max(query(descendants[1][0], 2), query(descendants[1][1], 2)) - 1;
    }

    std::cout << "! " << result << std::endl;
}

提出情報

ジャッジ結果