Download docker_space/frontier_cs_10/examples/gemini2.5pro_1.cpp from JustinTX/shinka-backup: direct link, hf CLI and curl.
- Browser
- Download file 2.82 kB
-
https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/gemini2.5pro_1.cpp
- Command line
-
hf download hf://JustinTX/shinka-backup/docker_space/frontier_cs_10/examples/gemini2.5pro_1.cpp
-
curl -L -o gemini2.5pro_1.cpp https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/gemini2.5pro_1.cpp
2.82 kB
| using namespace std; | |
| long long query(int u, int v) { | |
| cout << "? " << u << " " << v << endl; | |
| long long dist; | |
| cin >> dist; | |
| return dist; | |
| } | |
| struct Edge { | |
| int u, v, w; | |
| }; | |
| void solve() { | |
| int n; | |
| cin >> n; | |
| if (n == 1) { | |
| cout << "!" << endl; | |
| return; | |
| } | |
| vector<long long> d(n + 1, 0); | |
| for (int i = 2; i <= n; ++i) { | |
| d[i] = query(1, i); | |
| } | |
| vector<pair<long long, int>> sorted_vertices; | |
| for (int i = 2; i <= n; ++i) { | |
| sorted_vertices.push_back({d[i], i}); | |
| } | |
| sort(sorted_vertices.begin(), sorted_vertices.end()); | |
| vector<int> p(n + 1, 0); | |
| vector<vector<int>> children(n + 1); | |
| vector<Edge> edges; | |
| if (n > 1) { | |
| int v2 = sorted_vertices[0].second; | |
| p[v2] = 1; | |
| children[1].push_back(v2); | |
| edges.push_back({1, v2, (int)d[v2]}); | |
| } | |
| for (size_t i = 1; i < sorted_vertices.size(); ++i) { | |
| int v = sorted_vertices[i].second; | |
| int u = sorted_vertices[i - 1].second; | |
| long long dist_uv = query(u, v); | |
| long long d_lca = (d[u] + d[v] - dist_uv) / 2; | |
| int curr = u; | |
| while (d[curr] > d_lca) { | |
| curr = p[curr]; | |
| } | |
| int lca = curr; | |
| curr = lca; | |
| while (true) { | |
| int next_node = -1; | |
| int child_on_path_to_u = -1; | |
| if (curr != u) { | |
| int temp = u; | |
| while (p[temp] != curr) { | |
| temp = p[temp]; | |
| } | |
| child_on_path_to_u = temp; | |
| } | |
| // To make search potentially faster, process children in a random order | |
| vector<int> current_children = children[curr]; | |
| random_shuffle(current_children.begin(), current_children.end()); | |
| for (int child : current_children) { | |
| if (child == child_on_path_to_u) continue; | |
| long long dist_child_v = query(child, v); | |
| if (d[v] - d[child] == dist_child_v) { | |
| next_node = child; | |
| break; | |
| } | |
| } | |
| if (next_node != -1) { | |
| curr = next_node; | |
| } else { | |
| p[v] = curr; | |
| children[curr].push_back(v); | |
| edges.push_back({curr, v, (int)(d[v] - d[curr])}); | |
| break; | |
| } | |
| } | |
| } | |
| cout << "!"; | |
| for (const auto& edge : edges) { | |
| cout << " " << edge.u << " " << edge.v << " " << edge.w; | |
| } | |
| cout << endl; | |
| } | |
| int main() { | |
| ios_base::sync_with_stdio(false); | |
| cin.tie(NULL); | |
| int t; | |
| cin >> t; | |
| while (t--) { | |
| solve(); | |
| } | |
| return 0; | |
| } |