File size: 2,574 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 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | #include <bits/stdc++.h>
using namespace std;
static inline void die() {
exit(0);
}
struct Solver {
long long query(int u, int v) {
cout << "? " << u << " " << v << "\n";
cout.flush();
long long d;
if (!(cin >> d)) die();
if (d == -1) die();
return d;
}
void solve_one(int n) {
if (n <= 1) {
cout << "!\n";
cout.flush();
return;
}
vector<long long> depth(n + 1, 0);
for (int i = 2; i <= n; i++) depth[i] = query(1, i);
vector<int> order;
order.reserve(max(0, n - 1));
for (int i = 2; i <= n; i++) order.push_back(i);
sort(order.begin(), order.end(), [&](int a, int b) {
if (depth[a] != depth[b]) return depth[a] < depth[b];
return a < b;
});
vector<vector<int>> children(n + 1);
vector<int> parent(n + 1, 0);
vector<long long> wpar(n + 1, 0);
parent[1] = 0;
wpar[1] = 0;
for (int v : order) {
int cur = 1;
while (true) {
int found = 0;
int found_idx = -1;
auto &ch = children[cur];
for (int idx = 0; idx < (int)ch.size(); idx++) {
int c = ch[idx];
if (depth[c] >= depth[v]) continue;
long long d = query(c, v);
if (depth[c] + d == depth[v]) {
found = c;
found_idx = idx;
break;
}
}
if (!found) {
parent[v] = cur;
wpar[v] = depth[v] - depth[cur];
children[cur].push_back(v);
break;
} else {
// Move-to-front heuristic to reduce scans on repeated usage
if (found_idx > 0) swap(children[cur][0], children[cur][found_idx]);
cur = found;
}
}
}
cout << "!";
for (int i = 2; i <= n; i++) {
cout << " " << parent[i] << " " << i << " " << wpar[i];
}
cout << "\n";
cout.flush();
}
void run() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (!(cin >> T)) return;
while (T--) {
int n;
if (!(cin >> n)) die();
solve_one(n);
}
}
};
int main() {
Solver s;
s.run();
return 0;
} |