Task: | Distance Code |
Sender: | Carl Westerlund |
Submission time: | 2019-03-06 13:04:32 +0200 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 21 |
#2 | ACCEPTED | 47 |
#3 | ACCEPTED | 32 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#7 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#9 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#10 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#11 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#12 | ACCEPTED | 0.02 s | 2, 3 | details |
#13 | ACCEPTED | 0.01 s | 2, 3 | details |
#14 | ACCEPTED | 0.02 s | 2, 3 | details |
#15 | ACCEPTED | 0.01 s | 2, 3 | details |
#16 | ACCEPTED | 0.05 s | 3 | details |
#17 | ACCEPTED | 0.05 s | 3 | details |
#18 | ACCEPTED | 0.05 s | 3 | details |
#19 | ACCEPTED | 0.06 s | 3 | details |
#20 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
Code
#include <bits/stdc++.h>using namespace std;#if DEBUG#include "prettyprint.hpp"#define PRINTLN(x) \cerr << x << "\n"#define PRINTSP(x) \cerr << x << " "#else#define PRINTLN(x)#define PRINTSP(x)#endif#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define PI 3.141592653589793238462643template<class T> void amax(T & a, const T & b) { a = max(a,b); }template<class T> void amin(T & a, const T & b) { a = min(a,b); }int main() {ios_base::sync_with_stdio(false);cin.tie(NULL);int r = 0;int cas, N;cin >> cas >> N;if (cas == 1) {vector<vector<int>> neis (N);for (int n=0; n < N-1; n++) {int a, b;cin >> a >> b;neis[a-1].push_back(b-1);neis[b-1].push_back(a-1);}vector<int> p (N, -1);vector<vector<int>> chs (N);vector<bool> vis (N, 0);queue<int> q;q.push(r);while (!q.empty()) {int cur = q.front(); q.pop();if (!vis[cur]) {vis[cur] = 1;for (auto nei : neis[cur]) {if (nei != p[cur]) {q.push(nei);p[nei] = cur;chs[cur].push_back(nei);}}}}int cur = r;for (int i=0; i < N; i++) {while (!chs[cur].empty()) {int ncur = chs[cur].back();chs[cur].pop_back();cur = ncur;}cout << cur+1 << " ";cur = p[cur];}}else {vector<int> p (N, -1);int cur = r;vector<int> ds (N-1);for (int n=0; n < N-1; n++) {cin >> ds[n];}for (int n=N-2; n >= 0; n--) {int d = ds[n];for (int i=0; i < d-1; i++) {cur = p[cur];}p[n+1] = cur;cout << n+2 << " " << cur+1 << "\n";cur = n+1;}}}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 2 2 1 |
correct output |
---|
(empty) |
user output |
---|
2 1 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 3 3 1 2 1 |
correct output |
---|
(empty) |
user output |
---|
3 1 2 1 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 4 3 2 2 1 4 1 |
correct output |
---|
(empty) |
user output |
---|
4 1 3 4 2 1 |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 4 2 3 3 4 1 3 |
correct output |
---|
(empty) |
user output |
---|
4 1 3 4 2 4 |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 5 3 5 4 1 1 3 ... |
correct output |
---|
(empty) |
user output |
---|
5 1 4 5 3 1 2 3 |
Test 6
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 5 3 2 3 4 5 1 ... |
correct output |
---|
(empty) |
user output |
---|
5 1 4 1 3 4 2 4 |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 5 4 3 1 4 4 2 ... |
correct output |
---|
(empty) |
user output |
---|
5 1 4 5 3 5 2 5 |
Test 8
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 10 9 3 8 9 2 9 ... |
correct output |
---|
(empty) |
user output |
---|
10 1 9 10 8 10 7 10 6 10 ... |
Test 9
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 10 9 2 5 8 7 1 ... |
correct output |
---|
(empty) |
user output |
---|
10 1 9 10 8 9 7 8 6 7 ... |
Test 10
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 10 10 4 9 1 4 7 ... |
correct output |
---|
(empty) |
user output |
---|
10 1 9 1 8 9 7 1 6 7 ... |
Test 11
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 10 2 6 4 3 3 5 ... |
correct output |
---|
(empty) |
user output |
---|
10 1 9 10 8 9 7 8 6 7 ... |
Test 12
Group: 2, 3
Verdict: ACCEPTED
input |
---|
1 500 10 6 6 255 6 428 ... |
correct output |
---|
(empty) |
user output |
---|
500 1 499 500 498 500 497 500 496 500 ... Truncated |
Test 13
Group: 2, 3
Verdict: ACCEPTED
input |
---|
1 500 152 466 451 313 158 479 ... |
correct output |
---|
(empty) |
user output |
---|
500 1 499 500 498 499 497 498 496 497 ... Truncated |
Test 14
Group: 2, 3
Verdict: ACCEPTED
input |
---|
1 500 109 440 330 190 443 161 ... |
correct output |
---|
(empty) |
user output |
---|
500 1 499 1 498 499 497 498 496 498 ... Truncated |
Test 15
Group: 2, 3
Verdict: ACCEPTED
input |
---|
1 500 144 373 257 233 341 318 ... |
correct output |
---|
(empty) |
user output |
---|
500 1 499 500 498 499 497 498 496 497 ... Truncated |
Test 16
Group: 3
Verdict: ACCEPTED
input |
---|
1 100000 54983 75172 93807 75172 44082 75172 ... |
correct output |
---|
(empty) |
user output |
---|
100000 1 99999 100000 99998 100000 99997 100000 99996 100000 ... Truncated |
Test 17
Group: 3
Verdict: ACCEPTED
input |
---|
1 100000 88863 19059 86423 76688 98536 95984 ... |
correct output |
---|
(empty) |
user output |
---|
100000 1 99999 100000 99998 99999 99997 99998 99996 99997 ... Truncated |
Test 18
Group: 3
Verdict: ACCEPTED
input |
---|
1 100000 59979 6389 19097 24999 27846 82330 ... |
correct output |
---|
(empty) |
user output |
---|
100000 1 99999 1 99998 99999 99997 99998 99996 99998 ... Truncated |
Test 19
Group: 3
Verdict: ACCEPTED
input |
---|
1 100000 58761 66001 25102 51081 98625 67861 ... |
correct output |
---|
(empty) |
user output |
---|
100000 1 99999 100000 99998 99999 99997 99998 99996 99997 ... Truncated |
Test 20
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 6 2 1 3 2 4 2 ... |
correct output |
---|
(empty) |
user output |
---|
6 1 5 6 4 5 3 5 2 6 |