File size: 2,205 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 | #include <bits/stdc++.h>
using namespace std;
void build(int root, vector<int> S, const vector<long long>& dist, vector<tuple<int, int, long long>>& edges, int n) {
if (S.empty()) return;
sort(S.begin(), S.end(), [&](int x, int y) {
return dist[x] < dist[y];
});
vector<int> direct_children;
vector<vector<int>> subs;
for (int v : S) {
bool found = false;
for (size_t j = 0; j < direct_children.size(); ++j) {
int c = direct_children[j];
cout << "? " << c << " " << v << endl;
cout.flush();
long long dd;
cin >> dd;
long long expected = dist[v] - dist[c];
if (dd == expected) {
subs[j].push_back(v);
found = true;
break;
}
}
if (!found) {
direct_children.push_back(v);
subs.emplace_back();
long long w = dist[v] - dist[root];
edges.emplace_back(root, v, w);
}
}
for (size_t j = 0; j < direct_children.size(); ++j) {
int c = direct_children[j];
vector<int> sub = subs[j];
if (!sub.empty()) {
build(c, sub, dist, edges, n);
}
}
}
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;
if (n == 1) {
cout << "!" << endl;
cout.flush();
continue;
}
vector<long long> dist(n + 1, 0LL);
for (int j = 2; j <= n; ++j) {
cout << "? 1 " << j << endl;
cout.flush();
cin >> dist[j];
}
vector<int> all_nodes(n - 1);
iota(all_nodes.begin(), all_nodes.end(), 2);
sort(all_nodes.begin(), all_nodes.end(), [&](int x, int y) {
return dist[x] < dist[y];
});
vector<tuple<int, int, long long>> edges;
build(1, all_nodes, dist, edges, n);
cout << "!";
for (auto [u, v, w] : edges) {
cout << " " << u << " " << v << " " << w;
}
cout << endl;
cout.flush();
}
return 0;
} |