Download docker_space/frontier_cs_10/examples/gpt5_3.cpp from JustinTX/shinka-backup: direct link, hf CLI and curl.
- Browser
- Download file 2.46 kB
-
https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/gpt5_3.cpp
- Command line
-
hf download hf://JustinTX/shinka-backup/docker_space/frontier_cs_10/examples/gpt5_3.cpp
-
curl -L -o gpt5_3.cpp https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/gpt5_3.cpp
2.46 kB
| using namespace std; | |
| 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<vector<long long>> d(n + 1, vector<long long>(n + 1, 0)); | |
| for (int i = 1; i <= n; ++i) d[i][i] = 0; | |
| for (int i = 1; i <= n; ++i) { | |
| for (int j = i + 1; j <= n; ++j) { | |
| long long x; | |
| cin >> x; | |
| d[i][j] = d[j][i] = x; | |
| } | |
| } | |
| if (n == 1) { | |
| cout << "!\n"; | |
| continue; | |
| } | |
| vector<long long> dr(n + 1, 0); | |
| for (int i = 1; i <= n; ++i) dr[i] = d[1][i]; | |
| vector<pair<long long,int>> order; | |
| order.reserve(n); | |
| for (int i = 1; i <= n; ++i) order.push_back({dr[i], i}); | |
| sort(order.begin(), order.end()); | |
| vector<int> processed; | |
| processed.reserve(n); | |
| processed.push_back(1); | |
| vector<tuple<int,int,long long>> edges; | |
| edges.reserve(n - 1); | |
| for (auto &p : order) { | |
| int v = p.second; | |
| if (v == 1) continue; | |
| long long D = -1; | |
| int z = -1; | |
| for (int w : processed) { | |
| long long l = (dr[w] + dr[v] - d[w][v]) / 2; | |
| if (l > D) { | |
| D = l; | |
| z = (dr[w] == l ? w : -1); | |
| } else if (l == D) { | |
| if (z == -1 && dr[w] == l) z = w; | |
| } | |
| } | |
| if (z == -1) { | |
| // Fallback: choose any with max l, then find ancestor by scanning processed | |
| // but ideally shouldn't happen for valid tree metrics | |
| for (int w : processed) { | |
| long long l = (dr[w] + dr[v] - d[w][v]) / 2; | |
| if (l == D) { z = w; break; } | |
| } | |
| } | |
| long long wgt = dr[v] - D; | |
| if (z == -1) z = 1; // safeguard | |
| if (wgt < 0) wgt = 0; // safeguard | |
| edges.emplace_back(z, v, wgt); | |
| processed.push_back(v); | |
| } | |
| cout << "!"; | |
| for (auto &e : edges) { | |
| int u, v; | |
| long long w; | |
| tie(u, v, w) = e; | |
| cout << " " << u << " " << v << " " << w; | |
| } | |
| cout << "\n"; | |
| } | |
| return 0; | |
| } |