Task: | Distances |
Sender: | socho |
Submission time: | 2021-01-30 17:58:33 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 29 |
#2 | ACCEPTED | 71 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2 | details |
#2 | ACCEPTED | 0.02 s | 2 | details |
Compiler report
input/code.cpp: In function 'void solve()': input/code.cpp:83:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation] for (auto x: ord) cout << x << ' '; cout << endl; ^~~ input/code.cpp:83:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for' for (auto x: ord) cout << x << ' '; cout << endl; ^~~~ input/code.cpp: In function 'void usaco()': input/code.cpp:15:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result] freopen("problem.in", "r", stdin); ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~ input/code.cpp:16:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result] freopen("problem.out", "w", stdout); ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Code
#include <bits/stdc++.h>using namespace std;void fast() {ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);}void ran() {srand(chrono::steady_clock::now().time_since_epoch().count());}long long get_rand() {long long a = rand();long long b = rand();return a * (RAND_MAX + 1ll) + b;}void usaco() {freopen("problem.in", "r", stdin);freopen("problem.out", "w", stdout);}template<typename T>using min_pq = priority_queue<T, vector<T>, greater<T>>;// #define endl '\n'// #define double long double// #define int long long// const int MOD = 1000 * 1000 * 1000 + 7;// const int MOD = 998244353;int n;const int MXN = 105;vector<int> adj[MXN];int dist[MXN][MXN];int fr;void dfs(int node, int par, int dep) {dist[fr][node] = dep;for (auto x: adj[node]) {if (x == par) continue;dfs(x, node, dep+1);}}void solve() {for (int i=0; i<MXN; i++) adj[i].clear();cin >> n;for (int i=1; i<n; i++) {int a, b;cin >> a >> b;adj[a].push_back(b);adj[b].push_back(a);}for (int i=1; i<=n; i++) {fr = i;dfs(i, -1, 0);}vector<int> ord;ord.push_back(1);bool taken[n+1];memset(taken, 0, sizeof taken);taken[1] = true;for (int tri=0; tri<n-1; tri++) {int x = ord.back();int deepest = -1;for (int i=1; i<=n; i++) {if (taken[i]) continue;if (dist[x][i] > 3) continue;if (dist[1][i] > dist[1][deepest]) {deepest = i;}}assert(deepest != -1);taken[deepest] = true;ord.push_back(deepest);}for (auto x: ord) cout << x << ' '; cout << endl;}signed main() {ran(); fast();int t;cin >> t;while (t--) solve();}
Test details
Test 1
Group: 1, 2
Verdict: ACCEPTED
input |
---|
100 8 5 2 2 3 3 7 ... |
correct output |
---|
1 8 2 5 6 7 3 4 1 7 2 8 3 6 4 5 1 4 6 2 7 5 8 3 1 8 3 2 4 7 6 5 1 6 4 7 5 2 3 8 ... |
user output |
---|
1 3 5 6 2 7 8 4 1 8 2 7 3 4 6 5 1 8 7 2 5 6 3 4 1 3 2 4 7 8 5 6 1 3 5 2 7 4 6 8 ... Truncated |
Test 2
Group: 2
Verdict: ACCEPTED
input |
---|
100 100 37 59 81 37 44 81 ... |
correct output |
---|
1 99 82 81 59 5 71 55 17 24 13... |
user output |
---|
1 60 12 11 47 93 19 68 15 21 3... Truncated |