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

### Compiler report

```input/code.cpp: In function 'void search(int)':
input/code.cpp:82:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
~~~~~~~~~~~~~~^~~~```

### Code

```#include <iostream>
#include <algorithm>
#include <vector>

typedef long long ll;
using namespace std;

int n;

vector<vector<int>> vieruslista;

ll d[101][101];
ll v[101][101];

int z[101];

void calculateDistances() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i==j) d[i][j] = 0;
else if (v[i][j]) d[i][j] = v[i][j];
else d[i][j] = 1e18;
}
}

for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
}
}
}

vieruslista.clear();
vieruslista.resize(n+1);
for (int i = 1; i <= n; i++) {
for (int j = i+1; j <= n; j++) {
if (d[i][j] <= 3) {
vieruslista[i].push_back(j);
vieruslista[j].push_back(i);
}
}
}
}

cin >> n;

for (int i = 0; i < 101; i++) z[i] = 0;

for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
v[i][j] = 0;
v[j][i] = 0;
d[i][j] = 0;
d[j][i] = 0;
}
}

for (int i = 0; i < n-1; i++) {
int a, b; cin>>a>>b;
v[a][b] = 1;
v[b][a] = 1;
}
}

bool found = false;

void search(int s) {
//cout << "Solmu " << s << "\n";
if (found) return;
z[s] = 1;

//cout << "here " << s << "\n";
//for (int x : answer) cout << x << " ";
//cout << "\n";

found = true;
for (int x : answer) cout << x << " ";
cout << "\n";
//cout << "found";
return;
}

for (int u : vieruslista[s]) {
//cout << "Solmu " << u << "\n";
if (z[u]) continue;
//cout << "Solmujen etäisyys " << d[s][u] << "\n";
//cout << "Etsitään " << u << "\n";
search(u);

}

z[s] = 0;
}

int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);

int t; cin>>t;

for (int i = 0; i < t; i++) {
calculateDistances();

//while (true) {
// int a, b; cin >> a >> b;
//  cout << "Etäisyys " << d[a][b] << "\n";
//}

for (int i = 1; i <= n; i++) {
found = false;
search(i);
if (found) break;
}
}
}```

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