In Educational Codeforces Round 171 (Rated for Div. 2)

Thomas01 Thomas50 Thomas22 kdoaf023m

as you can see same timing and same solution, it is very weird since they are not even trying to hide it, I wonder if they are just stress testing plag checker of codeforces at this point.

I have already seen the tutorial and solved this question 2001C - Guess The Tree but I am still curious about what I did wrong in my original approach 277413780 because I feel that approach is correct, so if you can let me know my fault in approach or implementation, I will be grateful.

Thank You.

import sys
print = sys.stdout.write


t = int(input())
for i in range(t):
    n = int(input())
    child = []
    stack = []
    dic= [[0]*(n+1) for i in range(n+1)]
    for i in range(2,n+1):
        print(f"? {1} {i}\n")
        sys.stdout.flush()
        ans = int(input())
        if ans ==1:
            child.append((1,i))
        else:
            stack.append((1,ans,i))
        dic[i][1] = 1
        dic[1][i] = 1
    while stack:
        k = stack.pop()
        if dic[k[0]][k[1]] == 0 :
            print(f"? {k[0]} {k[1]}\n")
            sys.stdout.flush()
            ans = int(input())
            if ans == k[0]:
                child.append((k[0], k[1]))
            else:
                stack.append((k[0], ans, k[1]))
            dic[k[0]][k[1]] = 1
            dic[k[1]][k[0]] = 1
        if dic[k[2]][k[1]] == 0:
            print(f"? {k[1]} {k[2]}\n")
            sys.stdout.flush()
            ans = int(input())
            if ans == k[1]:
                child.append((k[1], k[2]))
            else:
                stack.append((k[1], ans, k[2]))
            dic[k[2]][k[1]] = 1
            dic[k[1]][k[2]] = 1
    print("! ")
    sys.stdout.flush()
    for a,b in child:
        print(f"{a} {b} ")
        sys.stdout.flush()
    print("\n")
    sys.stdout.flush()

Explaination:

dic matrix keeps track of what queries have already been made.

child keeps track of edges that have been found (some what misleading I know *_*).

stack keeps track of what queries have been made and their answer in format (a, answer, b) (if a and b are queries) and in turn what new queries need to be made.

the key difference from tutorial is after initial queries from 1 to {2 3 .... n} nodes I explore both sides of an answered query until I get an edge and keep track of it using dic and stack