CSES - Aalto Competitive Programming 2024 - wk2 - Wed - Results
Submission details
Task:Astralis session I
Sender:aalto2024b_003
Submission time:2024-09-11 17:16:19 +0300
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.01 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#8ACCEPTED0.01 sdetails
#9ACCEPTED0.01 sdetails
#10ACCEPTED0.01 sdetails
#11ACCEPTED0.01 sdetails
#12ACCEPTED0.01 sdetails
#13ACCEPTED0.01 sdetails
#14ACCEPTED0.01 sdetails
#15ACCEPTED0.01 sdetails
#16ACCEPTED0.01 sdetails
#17ACCEPTED0.01 sdetails
#18ACCEPTED0.01 sdetails
#19ACCEPTED0.01 sdetails
#20ACCEPTED0.01 sdetails
#21ACCEPTED0.01 sdetails
#22ACCEPTED0.01 sdetails
#23ACCEPTED0.01 sdetails
#24ACCEPTED0.01 sdetails
#25ACCEPTED0.01 sdetails
#26ACCEPTED0.01 sdetails
#27ACCEPTED0.01 sdetails
#28ACCEPTED0.01 sdetails
#29ACCEPTED0.01 sdetails
#30ACCEPTED0.01 sdetails
#31ACCEPTED0.01 sdetails
#32ACCEPTED0.01 sdetails
#33ACCEPTED0.01 sdetails
#34ACCEPTED0.01 sdetails
#35ACCEPTED0.01 sdetails
#36ACCEPTED0.01 sdetails
#37ACCEPTED0.01 sdetails
#38ACCEPTED0.01 sdetails
#39ACCEPTED0.01 sdetails
#40ACCEPTED0.01 sdetails
#41ACCEPTED0.01 sdetails
#42ACCEPTED0.01 sdetails
#43ACCEPTED0.01 sdetails
#44ACCEPTED0.01 sdetails
#45ACCEPTED0.01 sdetails
#46ACCEPTED0.01 sdetails
#47ACCEPTED0.01 sdetails
#48ACCEPTED0.01 sdetails
#49ACCEPTED0.01 sdetails
#50ACCEPTED0.01 sdetails
#51ACCEPTED0.01 sdetails
#52ACCEPTED0.06 sdetails
#53ACCEPTED0.06 sdetails
#54ACCEPTED0.06 sdetails
#55ACCEPTED0.06 sdetails
#56ACCEPTED0.07 sdetails
#57ACCEPTED0.06 sdetails
#58ACCEPTED0.06 sdetails
#59ACCEPTED0.06 sdetails
#60ACCEPTED0.06 sdetails
#61ACCEPTED0.06 sdetails

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long

string to_string(string s) {
    return '"' + s + '"';
}
 
string to_string(const char* s) {
    return to_string((string) s);
}
 
string to_string(bool b) {
    return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
 
void debug_out() {
    cerr << endl;
}
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n;
vector<int> adj[N];
int sz[N];
int ans[N];

void rec(int u, int p) {
    ans[u] = 1;
    for (int v : adj[u]) {
        if (v == p) continue;
        rec(v, u);
    }
}

void dfs(int u, int p = -1) {
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
    if (sz[u] == n / 2) {
        // ok
        cout << "Yes\n";
        rec(u, p);
        for (int i = 1; i <= n; i++) {
            if (ans[i]) cout << "U";
            else cout << "M";
        }
        cout << '\n';
        exit(0);
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }    

    dfs(1);
    cout << "No\n";
}

Test details

Test 1

Verdict: ACCEPTED

input
2
1 2

correct output
Yes
MU

user output
Yes
MU

Test 2

Verdict: ACCEPTED

input
6
1 3
2 3
2 6
4 6
...

correct output
No

user output
No

Test 3

Verdict: ACCEPTED

input
6
1 2
2 3
3 6
2 4
...

correct output
No

user output
No

Test 4

Verdict: ACCEPTED

input
6
1 6
1 4
2 4
2 3
...

correct output
No

user output
No

Test 5

Verdict: ACCEPTED

input
6
2 4
1 4
2 6
1 3
...

correct output
Yes
MUMUMU

user output
Yes
MUMUMU

Test 6

Verdict: ACCEPTED

input
8
1 8
5 8
3 5
3 6
...

correct output
Yes
MUMUMUUM

user output
Yes
MUMUMUUM

Test 7

Verdict: ACCEPTED

input
8
1 4
1 6
3 6
1 5
...

correct output
Yes
MUUMMUMU

user output
Yes
MUUMMUMU

Test 8

Verdict: ACCEPTED

input
8
1 7
1 3
1 8
2 8
...

correct output
No

user output
No

Test 9

Verdict: ACCEPTED

input
8
2 3
3 8
7 8
5 8
...

correct output
Yes
MMUMUMUU

user output
Yes
MMUMUMUU

Test 10

Verdict: ACCEPTED

input
10
4 8
4 7
1 7
3 4
...

correct output
Yes
MUMMMUMUUU

user output
Yes
MUMMMUMUUU

Test 11

Verdict: ACCEPTED

input
10
3 4
4 5
4 8
4 10
...

correct output
No

user output
No

Test 12

Verdict: ACCEPTED

input
10
1 3
2 3
2 6
6 10
...

correct output
Yes
MMMUUMUMUU

user output
Yes
MMMUUMUMUU

Test 13

Verdict: ACCEPTED

input
10
1 10
1 3
6 10
8 10
...

correct output
No

user output
No

Test 14

Verdict: ACCEPTED

input
10
1 6
1 4
2 4
2 9
...

correct output
No

user output
No

Test 15

Verdict: ACCEPTED

input
12
4 10
4 11
9 11
6 11
...

correct output
Yes
UUUMUMMUMUMM

user output
Yes
MMMUMUUMUMUU

Test 16

Verdict: ACCEPTED

input
12
1 2
1 8
5 8
3 8
...

correct output
Yes
MUMMMUUMUUUM

user output
Yes
MUMMMUUMUUUM

Test 17

Verdict: ACCEPTED

input
14
9 12
6 9
3 6
3 11
...

correct output
No

user output
No

Test 18

Verdict: ACCEPTED

input
14
13 14
7 13
3 7
7 10
...

correct output
Yes
UMMMMUMUUMUUMU

user output
Yes
MUUUUMUMMUMMUM

Test 19

Verdict: ACCEPTED

input
14
1 3
3 8
3 7
8 9
...

correct output
Yes
MUUUMMUUUMMMMU

user output
Yes
MUUUMMUUUMMMMU

Test 20

Verdict: ACCEPTED

input
16
4 12
1 4
12 16
11 12
...

correct output
No

user output
No

Test 21

Verdict: ACCEPTED

input
18
12 13
13 17
8 13
12 15
...

correct output
No

user output
No

Test 22

Verdict: ACCEPTED

input
100
24 28
28 65
28 58
54 65
...

correct output
Yes
MMUUMUMMUMUMUUMUUMMUUUMMMUUUUM...

user output
Yes
MMUUMUMMUMUMUUMUUMMUUUMMMUUUUM...
Truncated

Test 23

Verdict: ACCEPTED

input
100
57 98
24 57
24 34
25 34
...

correct output
Yes
MUUMUMUUUMMUMMUMUMMMMMUUUMUUMM...

user output
Yes
MUUMUMUUUMMUMMUMUMMMMMUUUMUUMM...
Truncated

Test 24

Verdict: ACCEPTED

input
100
6 41
6 20
6 18
6 88
...

correct output
Yes
MMMMUMMMUMUUMMUUUMMMUUUUUMUUUU...

user output
Yes
MMMMUMMMUMUUMMUUUMMMUUUUUMUUUU...
Truncated

Test 25

Verdict: ACCEPTED

input
100
24 100
92 100
62 100
88 100
...

correct output
Yes
MUUMMUUMMUMUMUMUUUUUUMMMUMUMUM...

user output
Yes
MUUMMUUMMUMUMUMUUUUUUMMMUMUMUM...
Truncated

Test 26

Verdict: ACCEPTED

input
100
65 83
68 83
65 87
21 65
...

correct output
No

user output
No

Test 27

Verdict: ACCEPTED

input
100
12 87
12 56
41 56
11 41
...

correct output
No

user output
No

Test 28

Verdict: ACCEPTED

input
100
13 29
13 38
13 34
10 13
...

correct output
Yes
MMMMUUMUMMUUMMUUMMMUMMUUMMUUUU...

user output
Yes
MMMMUUMUMMUUMMUUMMMUMMUUMMUUUU...
Truncated

Test 29

Verdict: ACCEPTED

input
100
77 94
52 77
53 77
53 56
...

correct output
No

user output
No

Test 30

Verdict: ACCEPTED

input
100
56 59
56 76
17 76
17 75
...

correct output
No

user output
No

Test 31

Verdict: ACCEPTED

input
100
19 70
70 86
27 86
27 31
...

correct output
Yes
MMMMUMMUMMUUMMUMUUUMMMUMUMUUMU...

user output
Yes
MMMMUMMUMMUUMMUMUUUMMMUMUMUUMU...
Truncated

Test 32

Verdict: ACCEPTED

input
200
28 148
28 122
28 137
122 178
...

correct output
Yes
UUMUMMMUUMMUMMMUMMUUMUMUMUMMMU...

user output
Yes
MMUMUUUMMUUMUUUMUUMMUMUMUMUUUM...
Truncated

Test 33

Verdict: ACCEPTED

input
200
57 98
57 153
34 153
98 109
...

correct output
No

user output
No

Test 34

Verdict: ACCEPTED

input
200
6 177
6 20
6 158
88 158
...

correct output
Yes
MUUMUMMMUMUUMUUUUUUMUMMMMUUMMU...

user output
Yes
MUUMUMMMUMUUMUUUUUUMUMMMMUUMMU...
Truncated

Test 35

Verdict: ACCEPTED

input
200
142 178
119 142
142 155
119 140
...

correct output
No

user output
No

Test 36

Verdict: ACCEPTED

input
200
83 150
68 83
68 158
135 158
...

correct output
Yes
MMMUUUUUUMUUUMUMUUMMMUMUUUMMUM...

user output
Yes
MMMUUUUUUMUUUMUMUUMMMUMUUUMMUM...
Truncated

Test 37

Verdict: ACCEPTED

input
200
20 177
87 177
121 177
137 177
...

correct output
Yes
MMUMUMMMUUUMUMUMMMUMUMUUUUUUMM...

user output
Yes
MMUMUMMMUUUMUMUMMMUMUMUUUUUUMM...
Truncated

Test 38

Verdict: ACCEPTED

input
200
13 139
13 38
13 34
10 38
...

correct output
Yes
MUMMUUMUUMUUMMUMMMMUMMUMUUUMMU...

user output
Yes
MUMMUUMUUMUUMMUMMMMUMMUMUUUMMU...
Truncated

Test 39

Verdict: ACCEPTED

input
200
84 198
77 198
52 198
53 77
...

correct output
Yes
MMMUMUMMMUUUUMUUUMMMMMUMUMUUUU...

user output
Yes
MMMUMUMMMUUUUMUUUMMMMMUMUMUUUU...
Truncated

Test 40

Verdict: ACCEPTED

input
200
56 112
76 112
56 182
56 114
...

correct output
No

user output
No

Test 41

Verdict: ACCEPTED

input
200
19 114
19 70
70 86
19 27
...

correct output
Yes
MMMUMUUUUUMUMMMMMMMUUMMUMMMMUM...

user output
Yes
MMMUMUUUUUMUMMMMMMMUUMMUMMMMUM...
Truncated

Test 42

Verdict: ACCEPTED

input
1000
811 883
397 883
137 397
546 883
...

correct output
Yes
MMMMMUUMUMUUUUUUMUMUMMMMUMMUMM...

user output
Yes
MMMMMUUMUMUUUUUUMUMUMMMMUMMUMM...
Truncated

Test 43

Verdict: ACCEPTED

input
1000
393 736
393 398
398 407
351 393
...

correct output
No

user output
No

Test 44

Verdict: ACCEPTED

input
1000
507 955
340 955
507 813
418 955
...

correct output
No

user output
No

Test 45

Verdict: ACCEPTED

input
1000
230 974
230 440
440 752
752 977
...

correct output
No

user output
No

Test 46

Verdict: ACCEPTED

input
1000
406 944
778 944
68 944
545 778
...

correct output
Yes
UMUMMUMUUMUUMUUMUMMUUMUUMUUUUM...

user output
Yes
MUMUUMUMMUMMUMMUMUUMMUMMUMMMMU...
Truncated

Test 47

Verdict: ACCEPTED

input
1000
771 921
368 921
121 921
121 810
...

correct output
Yes
UMMUUUUUMUMMUMUMUUUUMMMMUMUUMM...

user output
Yes
MUUMMMMMUMUUMUMUMMMMUUUUMUMMUU...
Truncated

Test 48

Verdict: ACCEPTED

input
1000
290 518
518 738
518 554
290 997
...

correct output
No

user output
No

Test 49

Verdict: ACCEPTED

input
1000
370 791
390 791
390 835
585 835
...

correct output
Yes
MMUUUUUMMMUMMUMMMMMMUUMMUMMMMU...

user output
Yes
MMUUUUUMMMUMMUMMMMMMUUMMUMMMMU...
Truncated

Test 50

Verdict: ACCEPTED

input
1000
111 804
778 804
520 804
520 829
...

correct output
Yes
MMMUMUUUUUMMMUMMMMMUUMMUMMUUUU...

user output
Yes
MMMUMUUUUUMMMUMMMMMUUMMUMMUUUU...
Truncated

Test 51

Verdict: ACCEPTED

input
1000
627 823
399 627
27 399
27 945
...

correct output
Yes
MMUMMMMUUMMUUMUUUUUMUMMUMMMMMU...

user output
Yes
MMUMMMMUUMMUUMUUUUUMUMMUMMMMMU...
Truncated

Test 52

Verdict: ACCEPTED

input
100000
26991 68205
21905 68205
3029 26991
21905 29288
...

correct output
No

user output
No

Test 53

Verdict: ACCEPTED

input
100000
41845 94618
94618 96640
65841 94618
9894 96640
...

correct output
Yes
UMUUUMMUUUMMUMMUMUMMMUMMMUMUMU...

user output
Yes
MUMMMUUMMMUUMUUMUMUUUMUUUMUMUM...
Truncated

Test 54

Verdict: ACCEPTED

input
100000
11081 29940
11081 90273
11081 56653
56653 73314
...

correct output
Yes
UMMUUMMMUUMMMMMUUMMUUUMUMMMUUU...

user output
Yes
MUUMMUUUMMUUUUUMMUUMMMUMUUUMMM...
Truncated

Test 55

Verdict: ACCEPTED

input
100000
27549 31873
27549 48777
48777 71940
48777 59266
...

correct output
Yes
MMMMUUMUUMUMUMMUUUMMUMMMUMUUUM...

user output
Yes
MMMMUUMUUMUMUMMUUUMMUMMMUMUUUM...
Truncated

Test 56

Verdict: ACCEPTED

input
100000
2460 57807
2460 59927
56550 59927
35046 56550
...

correct output
Yes
MMMUUMMUMMUUUMMUMUMMMUMUUMUMUM...

user output
Yes
MMMUUMMUMMUUUMMUMUMMMUMUUMUMUM...
Truncated

Test 57

Verdict: ACCEPTED

input
100000
13089 77222
77222 89616
36711 89616
27645 77222
...

correct output
Yes
UMUUUMMMUUUUMMUMMMUUMMUUMUMUMU...

user output
Yes
MUMMMUUUMMMMUUMUUUMMUUMMUMUMUM...
Truncated

Test 58

Verdict: ACCEPTED

input
100000
35805 70440
70440 82302
64483 82302
64483 96767
...

correct output
Yes
MMMUUMMMUUUMMMUUMUUMUMMUUUMUUM...

user output
Yes
MMMUUMMMUUUMMMUUMUUMUMMUUUMUUM...
Truncated

Test 59

Verdict: ACCEPTED

input
100000
16206 68738
37820 68738
55519 68738
55519 77758
...

correct output
Yes
MMUUUMUUMUUMUUMUMMMMMUMUUUUUUU...

user output
Yes
MMUUUMUUMUUMUUMUMMMMMUMUUUUUUU...
Truncated

Test 60

Verdict: ACCEPTED

input
100000
47137 86808
47137 80136
47137 73346
73346 78144
...

correct output
Yes
UUMUMMUUUUMMMMMMMMUUMMMMMMUUMU...

user output
Yes
MMUMUUMMMMUUUUUUUUMMUUUUUUMMUM...
Truncated

Test 61

Verdict: ACCEPTED

input
100000
39438 53660
53660 60245
20924 60245
20924 38669
...

correct output
No

user output
No