# NOI 2019 Open

 Start: N/A End: N/A

CSES - NOI 2019 Open - Results
History
1:49:47100
1:43:280
 Task: Distance Code Sender: jakob_nogler Submission time: 2019-03-09 20:43:57 Language: C++ Status: READY Score: 0

## Compiler report

```input/code.cpp: In function 'int main()':
input/code.cpp:62:36: warning: operation on 'cnt' may be undefined [-Wsequence-point]
dfs2(cnt, 0, 1, seq[i], cnt++);
~~~^~
```

## Code

```#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int N = 100005;

vi t[N], r1;
vpii r2;
bool found;
int seq[N];

void dfs1(int v, int f){
for(auto u : t[v])
if(u != f)
dfs1(u, v);
r1.pb(v);
}

void dfs2(int v, int f, int d, int td, int new_v){
if(td == d){
found = true;
r2.pb({v, new_v});
t[v].pb(new_v);
t[new_v].pb(v);
return;
}

for(auto u : t[v]){
if(u == v) continue;
dfs2(u, v, d + 1, td, new_v);
if(f) return;
}
}

int main(){
int k, n, a, b;
cin >> k >> n;
if(k == 1){
for(int i = 0; i < n - 1; i++){
cin >> a >> b;
t[a].pb(b);
t[b].pb(a);
}
dfs1(1, 0);
for(auto u : r1) cout << u << " ";
cout << endl;
return 0;
}

for(int i = 0; i < n - 1; i++) cin >> seq[i];

int cnt = 1;
for(int i = n - 1; i >= 0; i--){
found = false;
dfs2(cnt, 0, 1, seq[i], cnt++);
}

for(auto u : r2) cout << u.fi << " " << u.se << "\n";
}```

## Test details

### Test 1

Group: 1, 2, 3

input
```1 2 2 1```
view   save

correct output
(empty)
view   save

user output
`3 2`
view   save

### Test 2

Group: 1, 2, 3

input
```1 3 3 1 2 1```
view   save

correct output
(empty)
view   save

user output
`3 2`
view   save

### Test 3

Group: 1, 2, 3

input
```1 4 3 2 2 1 4 1```
view   save

correct output
(empty)
view   save

user output
```3 2 5 4```
view   save

### Test 4

Group: 1, 2, 3

input
```1 4 2 3 3 4 1 3```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3```
view   save

### Test 5

Group: 1, 2, 3

input
```1 5 3 5 4 1 1 3 4 2```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3 6 5```
view   save

### Test 6

Group: 1, 2, 3

input
```1 5 3 2 3 4 5 1 1 3```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3```
view   save

### Test 7

Group: 1, 2, 3

input
```1 5 4 3 1 4 4 2 5 4```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3```
view   save

### Test 8

Group: 1, 2, 3

input
```1 10 9 3 8 9 2 9 1 9 10 9 9 7 9 6 9 5 9 4```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3```
view   save

### Test 9

Group: 1, 2, 3

input
```1 10 9 2 5 8 7 1 6 8 4 10 9 7 10 3 3 2 1 6```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3 5 4 7 6 8 7 9 8 10 9 11 10```
view   save

### Test 10

Group: 1, 2, 3

input
```1 10 10 4 9 1 4 7 3 8 8 1 7 6 4 1 6 2 2 5```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3 5 4 6 5 7 6 10 9```
view   save

### Test 11

Group: 1, 2, 3

input
```1 10 2 6 4 3 3 5 10 6 9 2 7 5 1 8 7 8 1 2```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3 6 5 8 7 9 8 10 9 11 10```
view   save

### Test 12

Group: 2, 3

input
```1 500 10 6 6 255 6 428 7 6 65 6 157 6 326 6 6 108 273 6 6 238 485 6 217 6 390 6 6 437 356 6 6 433 6 290 6 50 ...```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3```
view   save

### Test 13

Group: 2, 3

input
```1 500 152 466 451 313 158 479 445 87 403 273 328 192 464 107 126 87 291 290 333 70 405 480 433 170 316 387 462 144 123 322 35 319 434 249 120 264 ...```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 ...```
view   save

### Test 14

Group: 2, 3

input
```1 500 109 440 330 190 443 161 206 81 236 23 390 191 262 270 385 130 287 137 267 278 107 412 244 392 425 214 348 262 312 210 229 156 351 387 338 112 ...```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3 5 4 6 5 7 6 8 7 11 10 12 11 13 12 16 15 17 16 19 18 20 19 23 22 24 23 25 24 27 26 29 28 30 29 31 30 ...```
view   save

### Test 15

Group: 2, 3

input
```1 500 144 373 257 233 341 318 156 159 185 13 53 470 432 16 308 263 94 302 136 297 197 323 294 347 168 268 41 455 32 330 380 276 266 91 269 187 ...```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 ...```
view   save

### Test 16

Group: 3

input
```1 100000 54983 75172 93807 75172 44082 75172 75172 84824 75172 98997 79024 75172 55343 75172 57592 75172 75172 29633 11325 75172 75172 41154 75172 51632 75172 24616 23798 75172 84117 75172 97734 75172 26832 75172 75172 95396 ...```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3```
view   save

### Test 17

Group: 3

input
```1 100000 88863 19059 86423 76688 98536 95984 96118 70092 42041 95469 79370 3245 54063 27564 50178 11587 37240 64983 68667 83518 62102 80017 74605 76124 78320 45225 17958 95419 89371 83327 85319 7806 80909 43525 22342 32749 ...```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 ...```
view   save

### Test 18

Group: 3

input
```1 100000 59979 6389 19097 24999 27846 82330 55283 21756 29532 76920 36672 78591 29233 30968 57832 78477 12306 933 80589 51575 39875 33992 73514 87981 87593 82747 84257 40591 14068 71832 42219 46584 67446 46486 17079 27619 ...```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3 5 4 6 5 7 6 8 7 10 9 11 10 12 11 14 13 15 14 17 16 19 18 20 19 21 20 22 21 24 23 25 24 27 26 28 27 ...```
view   save

### Test 19

Group: 3

input
```1 100000 58761 66001 25102 51081 98625 67861 39627 96609 42728 51847 40036 50769 80361 62871 83736 23954 90511 8565 43281 75921 10718 47821 82970 98999 95998 88339 55110 1439 77175 25851 55051 6725 78592 78169 20243 17805 ...```
view   save

correct output
(empty)
view   save

user output
```3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 21 20 22 21 23 22 ...```
view   save

### Test 20

Group: 1, 2, 3

```1 6 2 1 3 2 4 2 5 3 6 3```
```3 2 4 3 6 5```