QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#561635 | #9189. Make them Meet | ucup-team004 | 24 | 2ms | 3836kb | C++20 | 2.9kb | 2024-09-13 03:05:12 | 2024-09-13 03:05:13 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, M;
std::cin >> N >> M;
std::vector<std::vector<int>> adj(N);
for (int i = 0; i < M; i++) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
std::vector<bool> vis(N);
std::vector<int> dep(N), p(N);
p[0] = -1;
auto dfs = [&](auto &self, int x) -> void {
vis[x] = true;
for (auto y : adj[x]) {
if (!vis[y]) {
dep[y] = dep[x] + 1;
p[y] = x;
self(self, y);
}
}
};
dfs(dfs, 0);
int rt = std::max_element(dep.begin(), dep.end()) - dep.begin();
std::fill(vis.begin(), vis.end(), false);
std::fill(p.begin(), p.end(), -1);
dep[rt] = 0;
dfs(dfs, rt);
if (*std::max_element(dep.begin(), dep.end()) == N - 1) {
std::cout << 2 * N << "\n";
for (int i = 0; i < 2 * N; i++) {
for (int x = 0; x < N; x++) {
int c;
if (dep[x] % 2 == i % 2) {
c = x;
} else if (x != rt) {
c = p[x];
} else {
c = rt;
}
std::cout << c << " \n"[x == N - 1];
}
}
return 0;
}
int u = rt;
std::vector<int> deg(N);
for (int i = 1; i < N; i++) {
deg[p[i]]++;
}
for (int i = 0; i < N; i++) {
if (dep[i] > dep[u] && deg[i] > 1) {
u = i;
}
}
std::vector<bool> ef(N);
assert(u != rt);
int f = p[u];
for (auto y : adj[f]) {
ef[y] = true;
}
int v = -1;
for (int i = 0; i < N; i++) {
if (p[i] == u) {
if (v == -1 || !ef[i]) {
v = i;
}
}
}
assert(v != -1);
std::fill(vis.begin(), vis.end(), false);
dep[v] = 0;
std::swap(adj[v][0], *std::find(adj[v].begin(), adj[v].end(), u));
if (!ef[v]) {
std::swap(adj[u][0], *std::find(adj[u].begin(), adj[u].end(), f));
} else {
std::partition(adj[u].begin(), adj[u].end(),
[&](int i) {
return p[i] == u;
});
}
std::fill(p.begin(), p.end(), -1);
dfs(dfs, v);
std::cout << 2 * N << "\n";
for (int i = 0; i < 2 * N; i++) {
for (int x = 0; x < N; x++) {
int c;
if (dep[x] % 2 == i % 2) {
c = x;
} else if (x != v) {
c = p[x];
} else {
c = u;
}
std::cout << c << " \n"[x == N - 1];
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 10
Accepted
time: 0ms
memory: 3496kb
input:
2 1 0 1
output:
4 1 1 0 1 1 1 0 1
result:
points 1.0
Test #2:
score: 10
Accepted
time: 0ms
memory: 3504kb
input:
3 2 0 1 0 2
output:
6 1 1 2 0 1 0 1 1 2 0 1 0 1 1 2 0 1 0
result:
points 1.0
Test #3:
score: 0
Runtime Error
input:
4 3 0 1 0 2 0 3
output:
result:
Subtask #2:
score: 13
Accepted
Test #6:
score: 13
Accepted
time: 0ms
memory: 3776kb
input:
2 1 0 1
output:
4 1 1 0 1 1 1 0 1
result:
points 1.0
Test #7:
score: 13
Accepted
time: 0ms
memory: 3756kb
input:
3 3 1 2 0 1 0 2
output:
6 0 2 2 1 1 2 0 2 2 1 1 2 0 2 2 1 1 2
result:
points 1.0
Test #8:
score: 13
Accepted
time: 0ms
memory: 3764kb
input:
4 6 0 1 0 3 2 3 0 2 1 3 1 2
output:
8 0 0 2 2 3 1 2 3 0 0 2 2 3 1 2 3 0 0 2 2 3 1 2 3 0 0 2 2 3 1 2 3
result:
points 1.0
Test #9:
score: 13
Accepted
time: 0ms
memory: 3780kb
input:
10 45 4 9 2 8 5 9 1 2 2 9 4 5 5 7 6 7 1 3 1 9 3 4 0 3 4 7 0 6 5 6 7 9 4 8 6 8 0 5 1 8 3 9 1 6 6 9 4 6 0 8 2 3 0 4 0 9 0 7 3 6 0 2 2 5 3 7 3 5 7 8 5 8 8 9 0 1 2 7 1 7 1 4 2 6 2 4 3 8 1 5
output:
20 8 1 1 4 4 5 6 6 8 5 0 3 2 3 9 7 6 7 2 9 8 1 1 4 4 5 6 6 8 5 0 3 2 3 9 7 6 7 2 9 8 1 1 4 4 5 6 6 8 5 0 3 2 3 9 7 6 7 2 9 8 1 1 4 4 5 6 6 8 5 0 3 2 3 9 7 6 7 2 9 8 1 1 4 4 5 6 6 8 5 0 3 2 3 9 7 6 7 2 9 8 1 1 4 4 5 6 6 8 5 0 3 2 3 9 7 6 7 2 9 8 1 1 4 4 5 6 6 8 5 0 3 2 3 9 7 6 7 2 9 8 1 1 4 4 5 6 6 8...
result:
points 1.0
Test #10:
score: 13
Accepted
time: 0ms
memory: 3564kb
input:
15 105 4 10 8 13 0 12 11 12 2 13 8 14 6 10 0 4 8 12 2 12 1 13 5 9 2 8 7 10 6 13 0 13 9 13 7 11 3 13 0 3 4 7 5 13 7 13 0 7 0 11 0 8 0 2 2 4 2 6 6 9 0 1 9 11 1 9 3 14 3 4 10 11 5 10 0 9 3 9 6 11 2 10 5 6 2 5 1 14 6 8 9 12 2 11 9 10 5 12 5 14 4 14 7 14 5 8 5 7 1 12 0 14 7 9 3 11 1 8 0 10 1 3 8 9 4 6 10...
output:
30 3 1 4 3 4 5 6 7 8 6 7 12 12 1 8 0 1 2 14 10 9 2 11 13 9 10 11 0 13 14 3 1 4 3 4 5 6 7 8 6 7 12 12 1 8 0 1 2 14 10 9 2 11 13 9 10 11 0 13 14 3 1 4 3 4 5 6 7 8 6 7 12 12 1 8 0 1 2 14 10 9 2 11 13 9 10 11 0 13 14 3 1 4 3 4 5 6 7 8 6 7 12 12 1 8 0 1 2 14 10 9 2 11 13 9 10 11 0 13 14 3 1 4 3 4 5 6 7 8...
result:
points 1.0
Test #11:
score: 13
Accepted
time: 1ms
memory: 3664kb
input:
30 435 5 6 8 11 3 26 8 29 10 22 6 20 18 22 23 27 13 18 2 26 21 25 11 15 25 28 2 22 18 20 3 13 10 19 6 29 10 15 0 13 7 22 13 28 9 16 2 28 6 16 3 17 6 14 4 8 16 17 9 22 22 24 26 29 14 28 19 29 28 29 4 28 13 23 12 19 1 2 5 10 1 6 2 4 25 27 4 22 9 26 16 23 5 16 6 11 0 17 16 27 0 7 15 26 2 16 8 12 1 25 3...
output:
60 17 20 2 3 23 5 5 7 29 9 10 11 12 18 7 11 9 17 18 12 20 25 10 23 24 25 3 24 2 29 0 1 26 13 4 21 6 0 8 15 19 8 12 13 14 15 16 16 22 19 6 21 22 27 14 28 26 27 28 1 17 20 2 3 23 5 5 7 29 9 10 11 12 18 7 11 9 17 18 12 20 25 10 23 24 25 3 24 2 29 0 1 26 13 4 21 6 0 8 15 19 8 12 13 14 15 16 16 22 19 6 2...
result:
points 1.0
Test #12:
score: 13
Accepted
time: 1ms
memory: 3836kb
input:
40 780 21 24 11 32 12 27 19 20 3 35 25 35 32 35 27 33 0 24 1 3 1 29 14 25 8 30 24 31 14 32 7 12 5 31 28 35 7 10 18 24 13 32 1 26 3 4 10 30 14 38 22 24 9 31 5 10 17 32 2 34 28 39 3 38 13 34 6 10 0 6 9 25 11 14 13 20 10 20 18 28 6 33 34 35 29 33 16 39 4 38 3 24 20 29 17 18 33 36 13 37 24 27 12 33 5 29...
output:
80 0 3 2 3 38 5 0 7 30 15 7 11 27 13 11 15 16 16 18 19 29 21 5 23 18 25 26 27 28 29 30 26 13 23 21 25 2 19 38 28 36 1 34 35 4 31 6 12 8 9 10 32 12 37 14 22 39 17 17 20 20 24 22 23 24 8 6 33 4 1 10 31 32 33 34 35 36 37 14 39 0 3 2 3 38 5 0 7 30 15 7 11 27 13 11 15 16 16 18 19 29 21 5 23 18 25 26 27 2...
result:
points 1.0
Test #13:
score: 13
Accepted
time: 1ms
memory: 3512kb
input:
50 1225 6 10 14 36 0 34 7 23 22 31 18 34 2 19 13 21 0 46 0 11 2 43 2 11 13 20 13 19 7 39 35 37 9 17 31 38 13 40 7 28 2 41 20 46 25 36 12 39 1 37 21 42 33 48 10 24 13 26 26 37 0 47 17 19 1 28 28 40 15 40 11 22 10 19 24 28 12 28 19 40 6 12 13 48 20 37 11 46 8 19 5 24 16 28 15 47 31 34 11 21 28 33 14 1...
output:
100 0 28 2 3 4 33 6 7 8 17 24 22 12 13 18 47 8 17 18 40 46 13 22 7 24 36 30 49 28 29 30 44 42 33 0 37 36 37 3 12 40 6 42 2 44 29 46 47 4 49 11 1 19 16 43 5 10 39 27 9 10 11 25 20 14 15 16 35 34 19 20 21 31 23 5 25 26 27 26 32 45 31 32 48 34 35 14 23 38 39 15 41 21 43 44 45 9 1 48 41 0 28 2 3 4 33 6 ...
result:
points 1.0
Test #14:
score: 13
Accepted
time: 2ms
memory: 3720kb
input:
100 4950 24 39 27 46 11 71 57 65 3 8 84 97 74 87 17 49 12 72 1 4 22 83 29 42 28 65 39 89 29 92 26 78 45 53 18 44 33 43 14 98 50 66 21 95 32 67 21 33 21 80 59 77 70 85 13 16 0 41 31 65 51 80 22 80 30 79 55 75 54 82 29 57 72 97 31 85 86 87 60 90 1 17 65 81 13 15 44 71 58 88 65 87 8 31 77 99 4 44 29 43...
output:
200 76 17 59 3 4 5 66 46 75 9 10 11 12 13 37 13 69 17 18 19 20 21 93 78 24 25 99 36 98 29 63 85 67 33 25 3 36 37 94 24 9 41 5 33 4 53 46 47 48 48 41 51 47 53 54 81 10 65 58 59 60 83 18 63 19 65 66 67 96 69 20 11 89 12 74 75 76 79 78 79 51 81 54 83 97 85 86 86 58 89 60 74 29 93 94 21 96 97 98 99 0 1 ...
result:
points 1.0
Subtask #3:
score: 11
Accepted
Test #15:
score: 11
Accepted
time: 0ms
memory: 3812kb
input:
2 1 0 1
output:
4 1 1 0 1 1 1 0 1
result:
points 1.0
Test #16:
score: 11
Accepted
time: 0ms
memory: 3520kb
input:
3 2 0 1 1 2
output:
6 0 2 2 1 1 2 0 2 2 1 1 2 0 2 2 1 1 2
result:
points 1.0
Test #17:
score: 11
Accepted
time: 0ms
memory: 3624kb
input:
4 3 0 1 1 2 2 3
output:
8 1 1 3 3 0 2 2 3 1 1 3 3 0 2 2 3 1 1 3 3 0 2 2 3 1 1 3 3 0 2 2 3
result:
points 1.0
Test #18:
score: 11
Accepted
time: 1ms
memory: 3632kb
input:
49 48 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48
output:
98 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 46 46 48 48 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 48 0 2 2 4 4 6 6 8 8 10 1...
result:
points 1.0
Test #19:
score: 11
Accepted
time: 1ms
memory: 3596kb
input:
99 98 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 5...
output:
198 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 46 46 48 48 50 50 52 52 54 54 56 56 58 58 60 60 62 62 64 64 66 66 68 68 70 70 72 72 74 74 76 76 78 78 80 80 82 82 84 84 86 86 88 88 90 90 92 92 94 94 96 96 98 98 1 1 3 3 ...
result:
points 1.0
Test #20:
score: 11
Accepted
time: 1ms
memory: 3644kb
input:
100 99 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 ...
output:
200 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 99 99 0 2 2 ...
result:
points 1.0
Test #21:
score: 11
Accepted
time: 1ms
memory: 3772kb
input:
64 63 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 5...
output:
128 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 ...
result:
points 1.0
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%