CSES - Aalto Competitive Programming 2024 - wk2 - Wed

CSES - Aalto Competitive Programming 2024 - wk2 - Wed - Results

Submission details
Task:	Astralis session I
Sender:	aalto2024b_009
Submission time:	2024-09-11 17:19:24 +0300
Language:	PyPy3
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.04 s	details
#2	ACCEPTED	0.04 s	details
#3	ACCEPTED	0.04 s	details
#4	ACCEPTED	0.04 s	details
#5	ACCEPTED	0.04 s	details
#6	ACCEPTED	0.04 s	details
#7	ACCEPTED	0.04 s	details
#8	ACCEPTED	0.04 s	details
#9	ACCEPTED	0.04 s	details
#10	ACCEPTED	0.04 s	details
#11	ACCEPTED	0.04 s	details
#12	ACCEPTED	0.04 s	details
#13	ACCEPTED	0.04 s	details
#14	ACCEPTED	0.04 s	details
#15	ACCEPTED	0.04 s	details
#16	ACCEPTED	0.04 s	details
#17	ACCEPTED	0.04 s	details
#18	ACCEPTED	0.04 s	details
#19	ACCEPTED	0.04 s	details
#20	ACCEPTED	0.04 s	details
#21	ACCEPTED	0.04 s	details
#22	ACCEPTED	0.04 s	details
#23	ACCEPTED	0.04 s	details
#24	ACCEPTED	0.04 s	details
#25	ACCEPTED	0.05 s	details
#26	ACCEPTED	0.04 s	details
#27	ACCEPTED	0.04 s	details
#28	ACCEPTED	0.04 s	details
#29	ACCEPTED	0.04 s	details
#30	ACCEPTED	0.04 s	details
#31	ACCEPTED	0.04 s	details
#32	ACCEPTED	0.05 s	details
#33	ACCEPTED	0.04 s	details
#34	ACCEPTED	0.05 s	details
#35	ACCEPTED	0.04 s	details
#36	ACCEPTED	0.05 s	details
#37	ACCEPTED	0.05 s	details
#38	ACCEPTED	0.05 s	details
#39	ACCEPTED	0.05 s	details
#40	ACCEPTED	0.04 s	details
#41	ACCEPTED	0.05 s	details
#42	ACCEPTED	0.08 s	details
#43	ACCEPTED	0.07 s	details
#44	ACCEPTED	0.07 s	details
#45	ACCEPTED	0.07 s	details
#46	ACCEPTED	0.08 s	details
#47	ACCEPTED	0.07 s	details
#48	ACCEPTED	0.07 s	details
#49	ACCEPTED	0.07 s	details
#50	ACCEPTED	0.08 s	details
#51	ACCEPTED	0.07 s	details
#52	ACCEPTED	0.29 s	details
#53	ACCEPTED	0.39 s	details
#54	ACCEPTED	0.38 s	details
#55	ACCEPTED	0.38 s	details
#56	ACCEPTED	0.70 s	details
#57	ACCEPTED	0.38 s	details
#58	ACCEPTED	0.38 s	details
#59	ACCEPTED	0.59 s	details
#60	ACCEPTED	0.52 s	details
#61	ACCEPTED	0.42 s	details

Code

import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
g = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

root = 1

sums = [-1] * n
visited = [False] * n

parents = [-1] * n


def dfs(node):
    global sums
    if visited[node]:
        return
    visited[node] = True
    flag = 0
    for w in g[node]:
        if not visited[w]:
            parents[w] = node
            dfs(w)
            flag += sums[w]
    sums[node] = flag + 1


dfs(root)

k = n // 2

f = False
for i in range(n):
    if sums[i] == k:
        s = i
        # print('S', s)
        f = True
        break

if f:
    print('Yes')
    m = [False] * n
    visited = [False] * n
    visited[parents[s]] = True


    def dfs2(node):
        global m
        if visited[node]:
            return
        visited[node] = True
        for w in g[node]:
            if not visited[w]:
                m[w] = True
                dfs2(w)

    dfs2(s)

    # print(m)
    m[s] = True

    for j in range(n):
        if m[j]:
            print('M', end='')
        else:
            print('U', end='')
    print()
else:
    print('No')

Test details

Test 1

Verdict: ACCEPTED

input
`2 1 2` view save

correct output
`Yes MU` view save

user output
`Yes MU` view save

Test 2

Verdict: ACCEPTED

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

correct output
`No` view save

user output
`No` view save

Test 3

Verdict: ACCEPTED

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

correct output
`No` view save

user output
`No` view save

Test 4

Verdict: ACCEPTED

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

correct output
`No` view save

user output
`No` view save

Test 5

Verdict: ACCEPTED

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

correct output
`Yes MUMUMU` view save

user output
`Yes MUMUMU` view save

Test 6

Verdict: ACCEPTED

input
`8 1 8 5 8 3 5 3 6 ...` view save

correct output
`Yes MUMUMUUM` view save

user output
`Yes MUMUMUUM` view save

Test 7

Verdict: ACCEPTED

input
`8 1 4 1 6 3 6 1 5 ...` view save

correct output
`Yes MUUMMUMU` view save

user output
`Yes MUUMMUMU` view save

Test 8

Verdict: ACCEPTED

input
`8 1 7 1 3 1 8 2 8 ...` view save

correct output
`No` view save

user output
`No` view save

Test 9

Verdict: ACCEPTED

input
`8 2 3 3 8 7 8 5 8 ...` view save

correct output
`Yes MMUMUMUU` view save

user output
`Yes UUMUMUMM` view save

Test 10

Verdict: ACCEPTED

input
`10 4 8 4 7 1 7 3 4 ...` view save

correct output
`Yes MUMMMUMUUU` view save

user output
`Yes MUMMMUMUUU` view save

Test 11

Verdict: ACCEPTED

input
`10 3 4 4 5 4 8 4 10 ...` view save

correct output
`No` view save

user output
`No` view save

Test 12

Verdict: ACCEPTED

input
`10 1 3 2 3 2 6 6 10 ...` view save

correct output
`Yes MMMUUMUMUU` view save

user output
`Yes UUUMMUMUMM` view save

Test 13

Verdict: ACCEPTED

input
`10 1 10 1 3 6 10 8 10 ...` view save

correct output
`No` view save

user output
`No` view save

Test 14

Verdict: ACCEPTED

input
`10 1 6 1 4 2 4 2 9 ...` view save

correct output
`No` view save

user output
`No` view save

Test 15

Verdict: ACCEPTED

input
`12 4 10 4 11 9 11 6 11 ...` view save

correct output
`Yes UUUMUMMUMUMM` view save

user output
`Yes UUUMUMMUMUMM` view save

Test 16

Verdict: ACCEPTED

input
`12 1 2 1 8 5 8 3 8 ...` view save

correct output
`Yes MUMMMUUMUUUM` view save

user output
`Yes MUMMMUUMUUUM` view save

Test 17

Verdict: ACCEPTED

input
`14 9 12 6 9 3 6 3 11 ...` view save

correct output
`No` view save

user output
`No` view save

Test 18

Verdict: ACCEPTED

input
`14 13 14 7 13 3 7 7 10 ...` view save

correct output
`Yes UMMMMUMUUMUUMU` view save

user output
`Yes MUUUUMUMMUMMUM` view save

Test 19

Verdict: ACCEPTED

input
`14 1 3 3 8 3 7 8 9 ...` view save

correct output
`Yes MUUUMMUUUMMMMU` view save

user output
`Yes MUUUMMUUUMMMMU` view save

Test 20

Verdict: ACCEPTED

input
`16 4 12 1 4 12 16 11 12 ...` view save

correct output
`No` view save

user output
`No` view save

Test 21

Verdict: ACCEPTED

input
`18 12 13 13 17 8 13 12 15 ...` view save

correct output
`No` view save

user output
`No` view save

Test 22

Verdict: ACCEPTED

input
`100 24 28 28 65 28 58 54 65 ...` view save

correct output
`Yes MMUUMUMMUMUMUUMUUMMUUUMMMUUUUM...` view save

user output
`Yes UUMMUMUUMUMUMMUMMUUMMMUUUMMMMU...` view save

Test 23

Verdict: ACCEPTED

input
`100 57 98 24 57 24 34 25 34 ...` view save

correct output
`Yes MUUMUMUUUMMUMMUMUMMMMMUUUMUUMM...` view save

user output
`Yes MUUMUMUUUMMUMMUMUMMMMMUUUMUUMM...` view save

Test 24

Verdict: ACCEPTED

input
`100 6 41 6 20 6 18 6 88 ...` view save

correct output
`Yes MMMMUMMMUMUUMMUUUMMMUUUUUMUUUU...` view save

user output
`Yes UUUUMUUUMUMMUUMMMUUUMMMMMUMMMM...` view save

Test 25

Verdict: ACCEPTED

input
`100 24 100 92 100 62 100 88 100 ...` view save

correct output
`Yes MUUMMUUMMUMUMUMUUUUUUMMMUMUMUM...` view save

user output
`Yes MUUMMUUMMUMUMUMUUUUUUMMMUMUMUM...` view save

Test 26

Verdict: ACCEPTED

input
`100 65 83 68 83 65 87 21 65 ...` view save

correct output
`No` view save

user output
`No` view save

Test 27

Verdict: ACCEPTED

input
`100 12 87 12 56 41 56 11 41 ...` view save

correct output
`No` view save

user output
`No` view save

Test 28

Verdict: ACCEPTED

input
`100 13 29 13 38 13 34 10 13 ...` view save

correct output
`Yes MMMMUUMUMMUUMMUUMMMUMMUUMMUUUU...` view save

user output
`Yes UUUUMMUMUUMMUUMMUUUMUUMMUUMMMM...` view save

Test 29

Verdict: ACCEPTED

input
`100 77 94 52 77 53 77 53 56 ...` view save

correct output
`No` view save

user output
`No` view save

Test 30

Verdict: ACCEPTED

input
`100 56 59 56 76 17 76 17 75 ...` view save

correct output
`No` view save

user output
`No` view save

Test 31

Verdict: ACCEPTED

input
`100 19 70 70 86 27 86 27 31 ...` view save

correct output
`Yes MMMMUMMUMMUUMMUMUUUMMMUMUMUUMU...` view save

user output
`Yes UUUUMUUMUUMMUUMUMMMUUUMUMUMMUM...` view save

Test 32

Verdict: ACCEPTED

input
`200 28 148 28 122 28 137 122 178 ...` view save

correct output
`Yes UUMUMMMUUMMUMMMUMMUUMUMUMUMMMU...` view save

user output
`Yes UUMUMMMUUMMUMMMUMMUUMUMUMUMMMU...` view save

Test 33

Verdict: ACCEPTED

input
`200 57 98 57 153 34 153 98 109 ...` view save

correct output
`No` view save

user output
`No` view save

Test 34

Verdict: ACCEPTED

input
`200 6 177 6 20 6 158 88 158 ...` view save

correct output
`Yes MUUMUMMMUMUUMUUUUUUMUMMMMUUMMU...` view save

user output
`Yes MUUMUMMMUMUUMUUUUUUMUMMMMUUMMU...` view save

Test 35

Verdict: ACCEPTED

input
`200 142 178 119 142 142 155 119 140 ...` view save

correct output
`No` view save

user output
`No` view save

Test 36

Verdict: ACCEPTED

input
`200 83 150 68 83 68 158 135 158 ...` view save

correct output
`Yes MMMUUUUUUMUUUMUMUUMMMUMUUUMMUM...` view save

user output
`Yes UUUMMMMMMUMMMUMUMMUUUMUMMMUUMU...` view save

Test 37

Verdict: ACCEPTED

input
`200 20 177 87 177 121 177 137 177 ...` view save

correct output
`Yes MMUMUMMMUUUMUMUMMMUMUMUUUUUUMM...` view save

user output
`Yes UUMUMUUUMMMUMUMUUUMUMUMMMMMMUU...` view save

Test 38

Verdict: ACCEPTED

input
`200 13 139 13 38 13 34 10 38 ...` view save

correct output
`Yes MUMMUUMUUMUUMMUMMMMUMMUMUUUMMU...` view save

user output
`Yes MUMMUUMUUMUUMMUMMMMUMMUMUUUMMU...` view save

Test 39

Verdict: ACCEPTED

input
`200 84 198 77 198 52 198 53 77 ...` view save

correct output
`Yes MMMUMUMMMUUUUMUUUMMMMMUMUMUUUU...` view save

user output
`Yes UUUMUMUUUMMMMUMMMUUUUUMUMUMMMM...` view save

Test 40

Verdict: ACCEPTED

input
`200 56 112 76 112 56 182 56 114 ...` view save

correct output
`No` view save

user output
`No` view save

Test 41

Verdict: ACCEPTED

input
`200 19 114 19 70 70 86 19 27 ...` view save

correct output
`Yes MMMUMUUUUUMUMMMMMMMUUMMUMMMMUM...` view save

user output
`Yes UUUMUMMMMMUMUUUUUUUMMUUMUUUUMU...` view save

Test 42

Verdict: ACCEPTED

input
`1000 811 883 397 883 137 397 546 883 ...` view save

correct output
`Yes MMMMMUUMUMUUUUUUMUMUMMMMUMMUMM...` view save

user output
`Yes UUUUUMMUMUMMMMMMUMUMUUUUMUUMUU...` view save

Test 43

Verdict: ACCEPTED

input
`1000 393 736 393 398 398 407 351 393 ...` view save

correct output
`No` view save

user output
`No` view save

Test 44

Verdict: ACCEPTED

input
`1000 507 955 340 955 507 813 418 955 ...` view save

correct output
`No` view save

user output
`No` view save

Test 45

Verdict: ACCEPTED

input
`1000 230 974 230 440 440 752 752 977 ...` view save

correct output
`No` view save

user output
`No` view save

Test 46

Verdict: ACCEPTED

input
`1000 406 944 778 944 68 944 545 778 ...` view save

correct output
`Yes UMUMMUMUUMUUMUUMUMMUUMUUMUUUUM...` view save

user output
`Yes MUMUUMUMMUMMUMMUMUUMMUMMUMMMMU...` view save

Test 47

Verdict: ACCEPTED

input
`1000 771 921 368 921 121 921 121 810 ...` view save

correct output
`Yes UMMUUUUUMUMMUMUMUUUUMMMMUMUUMM...` view save

user output
`Yes MUUMMMMMUMUUMUMUMMMMUUUUMUMMUU...` view save

Test 48

Verdict: ACCEPTED

input
`1000 290 518 518 738 518 554 290 997 ...` view save

correct output
`No` view save

user output
`No` view save

Test 49

Verdict: ACCEPTED

input
`1000 370 791 390 791 390 835 585 835 ...` view save

correct output
`Yes MMUUUUUMMMUMMUMMMMMMUUMMUMMMMU...` view save

user output
`Yes UUMMMMMUUUMUUMUUUUUUMMUUMUUUUM...` view save

Test 50

Verdict: ACCEPTED

input
`1000 111 804 778 804 520 804 520 829 ...` view save

correct output
`Yes MMMUMUUUUUMMMUMMMMMUUMMUMMUUUU...` view save

user output
`Yes UUUMUMMMMMUUUMUUUUUMMUUMUUMMMM...` view save

Test 51

Verdict: ACCEPTED

input
`1000 627 823 399 627 27 399 27 945 ...` view save

correct output
`Yes MMUMMMMUUMMUUMUUUUUMUMMUMMMMMU...` view save

user output
`Yes UUMUUUUMMUUMMUMMMMMUMUUMUUUUUM...` view save

Test 52

Verdict: ACCEPTED

input
`100000 26991 68205 21905 68205 3029 26991 21905 29288 ...` view save

correct output
`No` view save

user output
`No` view save

Test 53

Verdict: ACCEPTED

input
`100000 41845 94618 94618 96640 65841 94618 9894 96640 ...` view save

correct output
`Yes UMUUUMMUUUMMUMMUMUMMMUMMMUMUMU...` view save

user output
`Yes MUMMMUUMMMUUMUUMUMUUUMUUUMUMUM...` view save

Test 54

Verdict: ACCEPTED

input
`100000 11081 29940 11081 90273 11081 56653 56653 73314 ...` view save

correct output
`Yes UMMUUMMMUUMMMMMUUMMUUUMUMMMUUU...` view save

user output
`Yes MUUMMUUUMMUUUUUMMUUMMMUMUUUMMM...` view save

Test 55

Verdict: ACCEPTED

input
`100000 27549 31873 27549 48777 48777 71940 48777 59266 ...` view save

correct output
`Yes MMMMUUMUUMUMUMMUUUMMUMMMUMUUUM...` view save

user output
`Yes UUUUMMUMMUMUMUUMMMUUMUUUMUMMMU...` view save

Test 56

Verdict: ACCEPTED

input
`100000 2460 57807 2460 59927 56550 59927 35046 56550 ...` view save

correct output
`Yes MMMUUMMUMMUUUMMUMUMMMUMUUMUMUM...` view save

user output
`Yes UUUMMUUMUUMMMUUMUMUUUMUMMUMUMU...` view save

Test 57

Verdict: ACCEPTED

input
`100000 13089 77222 77222 89616 36711 89616 27645 77222 ...` view save

correct output
`Yes UMUUUMMMUUUUMMUMMMUUMMUUMUMUMU...` view save

user output
`Yes MUMMMUUUMMMMUUMUUUMMUUMMUMUMUM...` view save

Test 58

Verdict: ACCEPTED

input
`100000 35805 70440 70440 82302 64483 82302 64483 96767 ...` view save

correct output
`Yes MMMUUMMMUUUMMMUUMUUMUMMUUUMUUM...` view save

user output
`Yes UUUMMUUUMMMUUUMMUMMUMUUMMMUMMU...` view save

Test 59

Verdict: ACCEPTED

input
`100000 16206 68738 37820 68738 55519 68738 55519 77758 ...` view save

correct output
`Yes MMUUUMUUMUUMUUMUMMMMMUMUUUUUUU...` view save

user output
`Yes UUMMMUMMUMMUMMUMUUUUUMUMMMMMMM...` view save

Test 60

Verdict: ACCEPTED

input
`100000 47137 86808 47137 80136 47137 73346 73346 78144 ...` view save

correct output
`Yes UUMUMMUUUUMMMMMMMMUUMMMMMMUUMU...` view save

user output
`Yes UUMUMMUUUUMMMMMMMMUUMMMMMMUUMU...` view save

Test 61

Verdict: ACCEPTED

input
`100000 39438 53660 53660 60245 20924 60245 20924 38669 ...` view save

correct output
`No` view save

user output
`No` view save

Aalto Competitive Programming 2024 - wk2 - Wed

Astralis session I

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Test 61

Tasks

Submissions (aalto2024b_009)