Download docker_space/frontier_cs_10/examples/gemini3pro_4.cpp from JustinTX/shinka-backup: direct link, hf CLI and curl.
- Browser
- Download file 4.6 kB
-
https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/gemini3pro_4.cpp
- Command line
-
hf download hf://JustinTX/shinka-backup/docker_space/frontier_cs_10/examples/gemini3pro_4.cpp
-
curl -L -o gemini3pro_4.cpp https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/gemini3pro_4.cpp
4.6 kB
| using namespace std; | |
| int n; | |
| vector<long long> dists; | |
| vector<int> p_node; | |
| vector<vector<int>> adj; | |
| vector<int> sub_sz; | |
| map<pair<int,int>, long long> memo; | |
| long long query(int u, int v) { | |
| if (u == v) return 0; | |
| if (u > v) swap(u, v); | |
| if (memo.count({u, v})) return memo[{u, v}]; | |
| cout << "? " << u << " " << v << endl; | |
| long long d; | |
| cin >> d; | |
| return memo[{u, v}] = d; | |
| } | |
| int get_heavy_leaf(int u) { | |
| while (!adj[u].empty()) { | |
| int best = -1, max_s = -1; | |
| for (int c : adj[u]) { | |
| if (sub_sz[c] > max_s) { | |
| max_s = sub_sz[c]; | |
| best = c; | |
| } | |
| } | |
| u = best; | |
| } | |
| return u; | |
| } | |
| int get_ancestor_at_depth(int u, long long d) { | |
| while (u != 0 && dists[u] > d) { | |
| u = p_node[u]; | |
| } | |
| return u; | |
| } | |
| void solve() { | |
| if (!(cin >> n)) return; | |
| memo.clear(); | |
| if (n == 1) { | |
| cout << "! " << endl; | |
| return; | |
| } | |
| dists.assign(n + 1, 0); | |
| for (int i = 2; i <= n; ++i) { | |
| dists[i] = query(1, i); | |
| } | |
| vector<int> nodes(n - 1); | |
| for (int i = 0; i < n - 1; ++i) nodes[i] = i + 2; | |
| sort(nodes.begin(), nodes.end(), [&](int a, int b) { | |
| return dists[a] < dists[b]; | |
| }); | |
| p_node.assign(n + 1, 0); | |
| adj.assign(n + 1, vector<int>()); | |
| sub_sz.assign(n + 1, 1); | |
| // Incrementally insert nodes | |
| for (int u : nodes) { | |
| int curr = 1; | |
| while (true) { | |
| if (adj[curr].empty()) { | |
| p_node[u] = curr; | |
| adj[curr].push_back(u); | |
| int tmp = u; | |
| while (tmp != 0) { | |
| sub_sz[tmp]++; | |
| tmp = p_node[tmp]; | |
| } | |
| break; | |
| } | |
| // Identify heavy child | |
| int heavy_child = -1, max_s = -1; | |
| for (int c : adj[curr]) { | |
| if (sub_sz[c] > max_s) { | |
| max_s = sub_sz[c]; | |
| heavy_child = c; | |
| } | |
| } | |
| // Query against a leaf in the heavy subtree | |
| int v = get_heavy_leaf(heavy_child); | |
| long long d_uv = query(u, v); | |
| long long lca_d = (dists[u] + dists[v] - d_uv) / 2; | |
| int w = get_ancestor_at_depth(v, lca_d); | |
| if (w != curr) { | |
| curr = w; | |
| // w is a descendant of curr, so we moved down the heavy path. | |
| // We know u branches off at w, and u is NOT in the child of w that leads to v. | |
| } | |
| // Identify the child of curr that leads to v (to exclude it) | |
| int child_towards_v = -1; | |
| int tmp = v; | |
| while (p_node[tmp] != curr) { | |
| tmp = p_node[tmp]; | |
| } | |
| child_towards_v = tmp; | |
| // Check other children (candidates) | |
| vector<int> candidates; | |
| for (int c : adj[curr]) { | |
| if (c != child_towards_v) candidates.push_back(c); | |
| } | |
| // Sort by size to check larger subtrees first (heuristic) | |
| sort(candidates.begin(), candidates.end(), [&](int a, int b){ | |
| return sub_sz[a] > sub_sz[b]; | |
| }); | |
| bool found = false; | |
| for (int c : candidates) { | |
| int v_prime = get_heavy_leaf(c); | |
| long long d_uv_p = query(u, v_prime); | |
| long long lca_d_p = (dists[u] + dists[v_prime] - d_uv_p) / 2; | |
| if (lca_d_p > dists[curr]) { | |
| // LCA is inside c's subtree | |
| curr = get_ancestor_at_depth(v_prime, lca_d_p); | |
| found = true; | |
| break; | |
| } | |
| } | |
| if (found) continue; | |
| // If not in any existing child's subtree, attach to curr | |
| p_node[u] = curr; | |
| adj[curr].push_back(u); | |
| tmp = u; | |
| while (tmp != 0) { | |
| sub_sz[tmp]++; | |
| tmp = p_node[tmp]; | |
| } | |
| break; | |
| } | |
| } | |
| cout << "!"; | |
| for (int i = 2; i <= n; ++i) { | |
| cout << " " << p_node[i] << " " << i << " " << (dists[i] - dists[p_node[i]]); | |
| } | |
| cout << endl; | |
| } | |
| int main() { | |
| ios_base::sync_with_stdio(false); | |
| cin.tie(NULL); | |
| int t; | |
| if (cin >> t) { | |
| while (t--) { | |
| solve(); | |
| } | |
| } | |
| return 0; | |
| } |