File size: 5,179 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 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 | #include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v;
long long w;
};
long long ask(int u, int v) {
if (u == v) return 0;
cout << "? " << u << " " << v << '\n';
cout.flush();
long long d;
if (!(cin >> d)) {
// In interactive environment, this should not happen.
exit(0);
}
return d;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (!(cin >> T)) return 0;
while (T--) {
int n;
if (!(cin >> n)) return 0;
vector<Edge> edges;
edges.reserve(max(0, n - 1));
if (n > 0) {
vector<vector<int>> stack;
vector<int> initial(n);
iota(initial.begin(), initial.end(), 1);
stack.push_back(std::move(initial));
while (!stack.empty()) {
vector<int> S = std::move(stack.back());
stack.pop_back();
int m = (int)S.size();
if (m <= 1) continue;
int A = S[0];
vector<long long> distA(m), distB(m);
long long D = 0;
int idxB = 0;
// First sweep: from A to find B and get distA.
for (int i = 0; i < m; ++i) {
int v = S[i];
if (v == A) {
distA[i] = 0;
} else {
distA[i] = ask(A, v);
}
if (distA[i] > D) {
D = distA[i];
idxB = i;
}
}
int B = S[idxB];
// Second sweep: from B to get distB.
for (int i = 0; i < m; ++i) {
int v = S[i];
if (v == B) {
distB[i] = 0;
} else {
distB[i] = ask(B, v);
}
}
// Collect nodes on path A-B.
vector<pair<long long, int>> pathNodes;
pathNodes.reserve(m);
for (int i = 0; i < m; ++i) {
if (distA[i] + distB[i] == D) {
pathNodes.emplace_back(distA[i], S[i]);
}
}
sort(pathNodes.begin(), pathNodes.end(),
[](const pair<long long,int> &x, const pair<long long,int> &y) {
return x.first < y.first;
});
// Add edges along the path.
for (int i = 1; i < (int)pathNodes.size(); ++i) {
int u = pathNodes[i - 1].second;
int v = pathNodes[i].second;
long long w = pathNodes[i].first - pathNodes[i - 1].first;
edges.push_back({u, v, w});
}
// Map distA on path to vertex.
unordered_map<long long, int> rootByDist;
rootByDist.reserve(pathNodes.size() * 2 + 1);
for (auto &p : pathNodes) {
rootByDist[p.first] = p.second;
}
// Group vertices by projection root on A-B path.
unordered_map<int, vector<int>> groups;
groups.reserve(pathNodes.size() * 2 + 1);
for (int i = 0; i < m; ++i) {
long long num = distA[i] + D - distB[i];
long long t = num / 2; // guaranteed integer in tree metric
int root;
auto it = rootByDist.find(t);
if (it != rootByDist.end()) {
root = it->second;
} else {
// Fallback (should not happen in correct tree metric)
auto it2 = lower_bound(
pathNodes.begin(), pathNodes.end(),
pair<long long,int>(t, -1),
[](const pair<long long,int>& a,
const pair<long long,int>& b) {
return a.first < b.first;
});
if (it2 != pathNodes.end() && it2->first == t) {
root = it2->second;
} else {
// As a very last resort, attach to nearest in terms of distA on path.
if (it2 == pathNodes.end()) --it2;
root = it2->second;
}
}
groups[root].push_back(S[i]);
}
// Recurse on each group (component).
for (auto &kv : groups) {
auto &comp = kv.second;
if (comp.size() <= 1) continue;
stack.push_back(std::move(comp));
}
}
}
cout << "!";
for (const auto &e : edges) {
cout << " " << e.u << " " << e.v << " " << e.w;
}
cout << '\n';
cout.flush();
}
return 0;
} |