File size: 2,573 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | #include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int n;
cin >> n;
vector<ll> D(n + 1, 0);
vector<tuple<int, int, ll>> edges;
queue<pair<int, vector<int>>> q;
vector<int> initial;
if (n >= 2) {
for (int j = 2; j <= n; j++) {
cout << "? 1 " << j << "\n";
cout.flush();
cin >> D[j];
}
for (int j = 2; j <= n; j++) initial.push_back(j);
q.push({1, initial});
}
while (!q.empty()) {
auto front = q.front();
q.pop();
int rt = front.first;
vector<int> dsc = front.second;
if (dsc.empty()) continue;
vector<int> current_active = dsc;
while (!current_active.empty()) {
int pivot = current_active[0];
vector<int> temp_remaining;
vector<int> same_group{pivot};
for (size_t j = 1; j < current_active.size(); j++) {
int u = current_active[j];
cout << "? " << pivot << " " << u << "\n";
cout.flush();
ll dd;
cin >> dd;
ll expected = D[pivot] + D[u] - 2LL * D[rt];
if (dd < expected) {
same_group.push_back(u);
} else {
temp_remaining.push_back(u);
}
}
current_active = temp_remaining;
int c = same_group[0];
ll minn = D[c];
for (int nd : same_group) {
if (D[nd] < minn) {
minn = D[nd];
c = nd;
}
}
ll w = D[c] - D[rt];
edges.emplace_back(rt, c, w);
vector<int> sub_dsc;
for (int nd : same_group) {
if (nd != c) sub_dsc.push_back(nd);
}
if (!sub_dsc.empty()) {
q.push({c, sub_dsc});
}
}
}
cout << "!";
for (auto& e : edges) {
int u, v;
ll w;
tie(u, v, w) = e;
cout << " " << u << " " << v << " " << w;
}
cout << "\n";
cout.flush();
}
return 0;
} |