Download docker_space/frontier_cs_10/examples/deepseekreasoner_4.cpp from JustinTX/shinka-backup: direct link, hf CLI and curl.
- Browser
- Download file 5.32 kB
-
https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/deepseekreasoner_4.cpp
- Command line
-
hf download hf://JustinTX/shinka-backup/docker_space/frontier_cs_10/examples/deepseekreasoner_4.cpp
-
curl -L -o deepseekreasoner_4.cpp https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/deepseekreasoner_4.cpp
5.32 kB
| using namespace std; | |
| const int MAXN = 100005; | |
| int parent[MAXN]; | |
| long long edge_weight[MAXN]; | |
| unordered_map<long long, long long> dist_cache; // key = u*(MAXN+1)+v | |
| long long query(int u, int v) { | |
| if (u == v) return 0; | |
| if (u > v) swap(u, v); | |
| long long key = 1LL * u * (MAXN + 1) + v; | |
| auto it = dist_cache.find(key); | |
| if (it != dist_cache.end()) return it->second; | |
| cout << "? " << u << " " << v << endl; | |
| cout.flush(); | |
| long long d; | |
| cin >> d; | |
| dist_cache[key] = d; | |
| return d; | |
| } | |
| struct Component { | |
| vector<int> nodes; | |
| int root; | |
| vector<long long> dists; // distance from root to each node in 'nodes' | |
| }; | |
| int main() { | |
| ios::sync_with_stdio(false); | |
| cin.tie(0); | |
| int T; | |
| cin >> T; | |
| while (T--) { | |
| int n; | |
| cin >> n; | |
| // reset | |
| dist_cache.clear(); | |
| for (int i = 1; i <= n; ++i) parent[i] = -1; | |
| // initial distances from node 1 | |
| vector<long long> dist1(n + 1, 0); | |
| for (int i = 2; i <= n; ++i) { | |
| dist1[i] = query(1, i); | |
| } | |
| // initial component: whole tree rooted at 1 | |
| vector<int> all_nodes(n); | |
| vector<long long> all_dists(n); | |
| for (int i = 0; i < n; ++i) { | |
| all_nodes[i] = i + 1; | |
| all_dists[i] = dist1[i + 1]; | |
| } | |
| Component init{all_nodes, 1, all_dists}; | |
| stack<Component> st; | |
| st.push(init); | |
| while (!st.empty()) { | |
| Component comp = st.top(); | |
| st.pop(); | |
| if (comp.nodes.size() <= 1) continue; | |
| // map node -> its distance from comp.root | |
| unordered_map<int, long long> dist_map; | |
| for (size_t i = 0; i < comp.nodes.size(); ++i) { | |
| dist_map[comp.nodes[i]] = comp.dists[i]; | |
| } | |
| // find farthest node from root (except root itself) | |
| int x = -1; | |
| long long max_dist = -1; | |
| for (int u : comp.nodes) { | |
| if (u == comp.root) continue; | |
| if (dist_map[u] > max_dist) { | |
| max_dist = dist_map[u]; | |
| x = u; | |
| } | |
| } | |
| if (x == -1) continue; | |
| // query distances from x to all nodes in this component | |
| unordered_map<int, long long> dist_x; | |
| for (int u : comp.nodes) { | |
| if (u == x) { | |
| dist_x[u] = 0; | |
| continue; | |
| } | |
| dist_x[u] = query(x, u); | |
| } | |
| long long d_root_x = dist_map[x]; | |
| // nodes on the path between root and x | |
| vector<int> path; | |
| for (int u : comp.nodes) { | |
| if (dist_map[u] + dist_x[u] == d_root_x) { | |
| path.push_back(u); | |
| } | |
| } | |
| sort(path.begin(), path.end(), [&](int a, int b) { | |
| return dist_map[a] < dist_map[b]; | |
| }); | |
| unordered_set<int> path_set(path.begin(), path.end()); | |
| // map distance from root -> node on path (unique) | |
| unordered_map<long long, int> dist_to_node; | |
| for (int u : path) { | |
| dist_to_node[dist_map[u]] = u; | |
| } | |
| // add edges along the path | |
| for (size_t i = 1; i < path.size(); ++i) { | |
| int a = path[i - 1]; | |
| int b = path[i]; | |
| if (parent[b] == -1) { | |
| parent[b] = a; | |
| edge_weight[b] = dist_map[b] - dist_map[a]; | |
| } | |
| } | |
| // group nodes by their foot on the path | |
| unordered_map<int, vector<int>> groups; | |
| for (int f : path) { | |
| groups[f].push_back(f); | |
| } | |
| for (int u : comp.nodes) { | |
| if (path_set.count(u)) continue; | |
| long long d_u_root = dist_map[u]; | |
| long long d_u_x = dist_x[u]; | |
| long long t = (d_u_root + d_root_x - d_u_x) / 2; | |
| int f = dist_to_node[t]; | |
| groups[f].push_back(u); | |
| } | |
| // create new components for each foot with more than one node | |
| for (auto& entry : groups) { | |
| int f = entry.first; | |
| vector<int>& nodes_list = entry.second; | |
| if (nodes_list.size() <= 1) continue; | |
| vector<int> new_nodes; | |
| vector<long long> new_dists; | |
| long long d_f_root = dist_map[f]; | |
| for (int u : nodes_list) { | |
| new_nodes.push_back(u); | |
| if (u == f) { | |
| new_dists.push_back(0); | |
| } else { | |
| new_dists.push_back(dist_map[u] - d_f_root); | |
| } | |
| } | |
| Component new_comp{new_nodes, f, new_dists}; | |
| st.push(new_comp); | |
| } | |
| } | |
| // output answer | |
| cout << "!"; | |
| for (int i = 2; i <= n; ++i) { | |
| cout << " " << parent[i] << " " << i << " " << edge_weight[i]; | |
| } | |
| cout << endl; | |
| cout.flush(); | |
| } | |
| return 0; | |
| } |