QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#561635#9189. Make them Meetucup-team00424 2ms3836kbC++202.9kb2024-09-13 03:05:122024-09-13 03:05:13

Judging History

你现在查看的是最新测评结果

  • [2024-09-13 03:05:13]
  • 评测
  • 测评结果:24
  • 用时:2ms
  • 内存:3836kb
  • [2024-09-13 03:05:12]
  • 提交

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%