CSES - Datatähti 2021 loppu - Results
 Task: Etäisyydet Sender: Mahtimursu Submission time: 2021-01-23 18:51:35 +0200 Language: C++11 Status: READY Result: 29
Feedback
groupverdictscore
#1ACCEPTED29
#20
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2--2details

### Code

#include <bits/stdc++.h>

typedef long long ll;

#define M 1000000007
#define N (1 << 18)

using namespace std;

int dst[101][101];
int n;
bool f = 0;
vector<int> v[101];

void find(int s, int cur, int e, int d) {
dst[s][cur] = d;
//cout << s << ", " << cur << " e: " << e << endl;
for (int u : v[cur]) {
if (u == e) continue;
find(s, u, cur, d + 1);
}
}

int order[101];
int vis[101];

void brute(int cur) {
if (f) return;
if (cur == n) {
for (int i = 0; i < n; ++i) {
cout << order[i] << " ";
}
f = 1;
return;
} else {
for (int i = 1; i <= n; ++i) {
if (vis[i]) continue;
if (dst[order[cur - 1]][i] > 3) continue;
vis[i] = 1;
order[cur] = i;
brute(cur + 1);
vis[i] = 0;
}
}
}

vector<pair<int, int>> nv[101];

void b2(int cur) {
if (f) return;
if (cur == n) {
for (int i = 0; i < n; ++i) {
cout << order[i] << " ";
}
f = 1;
return;
} else {
for (auto p : nv[order[cur - 1]]) {
int u = p.second;
if (vis[u]) continue;
vis[u] = 1;
order[cur] = u;
b2(cur + 1);
vis[u] = 0;
}
/*for (int i = 1; i <= n; ++i) {
if (vis[i]) continue;
if (dst[order[cur - 1]][i] > 3) continue;
vis[i] = 1;
order[cur] = i;
brute(cur + 1);
vis[i] = 0;
}*/
}
}

void test_case() {
f = 0;
cin >> n;
for (int i = 0; i <= n; ++i) {
v[i].clear();
}
for (int i = 1; i < n; ++i) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
//cout << "hre" << endl;
for (int i = 1; i <= n; ++i) {
find(i, i, -1, 0);
}

for (int i = 0; i <= n; ++i) {
v[i].clear();
nv[i].clear();
}

for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (i == j) continue;
if (dst[i][j] <= 3) {
v[i].push_back(j);
v[j].push_back(i);
}
}
}
vector<pair<int, int>> so;
for (int i = 1; i <= n; ++i) {
so.push_back({v[i].size(), i});
for (int u : v[i]) {
nv[i].push_back({v[u].size(), u});
}

sort(nv[i].begin(), nv[i].end());
}

sort(so.begin(), so.end());
//cout << "hre" << endl;

/*for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cout << "i: " << i << " j: " << j << " d:" << dst[i][j] << endl;
}
}*/

for (auto p : so) {
int i = p.second;
vis[i] = 1;
order[0] = i;
b2(1);
vis[i] = 0;
}

}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 0;
cin >> t;
for (int i = 0; i < t; ++i) {
test_case();
cout << "\n";
}

return 0;
}

### 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 4 2 5 6 7 3 8
2 8 7 5 4 6 1 3
4 1 3 2 7 5 8 6
3 1 5 2 4 6 7 8
5 2 7 8 6 1 3 4
...
Truncated

#### Test 2

Group: 2

Verdict:

input
100
100
37 59
81 37
44 81
...

correct output
1 99 82 81 59 5 71 55 17 24 13...

user output
(empty)