Submission #10679447


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

dist = [-1] * (N+1)
stack = [1]
dist[1] = 0
while stack:
    v = stack.pop()
    for w in graph[v]:
        if dist[w] == -1:
            dist[w] = dist[v] + 1
            stack.append(w)

ev = [i for i,x in enumerate(dist) if x % 2 == 0 and i > 0]
od = [i for i,x in enumerate(dist) if x % 2 == 1 and i > 0]

def make_perm(N, ev, od, x0, x1, x2, y0, y1, y2):
    assert len(ev) == x0 + x1 + x2
    assert len(od) == y0 + y1 + y2
    P = [0] * (N+1)
    for i in ev:
        if x0:
            P[i] = (x0 + y0) * 3
            x0 -= 1
            continue
        if x1:
            P[i] = (x1 + y1) * 3 - 2
            x1 -= 1
            continue
        if x2:
            P[i] = (x2 + y2) * 3 - 1
            x2 -= 1
            continue
    for i in od:
        if y0:
            P[i] = (x0 + y0) * 3
            y0 -= 1
            continue
        if y1:
            P[i] = (x1 + y1) * 3 - 2
            y1 -= 1
            continue
        if y2:
            P[i] = (x2 + y2) * 3 - 1
            y2 -= 1
            continue
    return P[1:]

def solve(N, ev, od):
    x0 = N // 3
    x1 = (N+2) // 3
    x2 = (N+1) // 3
    perm = [0] * (N+1)
    LE = len(ev)
    LO = len(od)
    if LE <= x0:
        return make_perm(N, ev, od, LE, 0, 0, x0-LE, x1, x2)
    if LO <= x0:
        return make_perm(N, ev, od, x0-LO, x1, x2, LO, 0, 0)
    if LE == x1:
        return make_perm(N, ev, od, 0, x1, 0, x0, 0, x2)
    if LO == x1:
        return make_perm(N, ev, od, x0, 0, x2, 0, x1, 0)
    # どちらも x1 よりたくさんある
    return make_perm(N, ev, od, LE-x1, x1, 0, LO-x2, 0, x2)

P = solve(N, ev, od)
print(' '.join(map(str, P)))

Submission Info

Submission Time
Task C - ThREE
User maspy
Language Python3 (3.4.3)
Score 600
Code Size 2001 Byte
Status
Exec Time 785 ms
Memory 73480 KB

Test Cases

Set Name Score / Max Score Test Cases
All 600 / 600 00_sample_01, 20_small_01, 20_small_02, 20_small_03, 20_small_04, 20_small_05, 30_large_01, 30_large_02, 30_large_03, 40_line_01, 40_line_02, 40_line_03, 50_star_01, 50_star_02, 50_star_03, 60_hand_01, 60_hand_02, 60_hand_03, 60_hand_04, 60_hand_05, 60_hand_06, 60_hand_07, 60_hand_08, 60_hand_09, 60_hand_10, 60_hand_11, 60_hand_12, 60_hand_13, 60_hand_14, 60_hand_15, 60_hand_16, 60_hand_17, 60_hand_18, 60_hand_19, 60_hand_20, 60_hand_21, 60_hand_22, 60_hand_23, 60_hand_24, 60_hand_25, 60_hand_26, 60_hand_27, 60_hand_28, 60_hand_29, 60_hand_30, 70_dense_01, 70_dense_02, 70_dense_03, 70_dense_04, 70_dense_05, 70_dense_06, 70_dense_07, 70_dense_08, 70_dense_09, 70_dense_10, 90_hand_01, 90_hand_02
sample 0 / 0 00_sample_01
Case Name Status Exec Time Memory
00_sample_01 17 ms 3192 KB
20_small_01 18 ms 3192 KB
20_small_02 18 ms 3192 KB
20_small_03 18 ms 3192 KB
20_small_04 18 ms 3192 KB
20_small_05 18 ms 3192 KB
30_large_01 785 ms 73480 KB
30_large_02 704 ms 72096 KB
30_large_03 698 ms 73216 KB
40_line_01 399 ms 59860 KB
40_line_02 362 ms 43032 KB
40_line_03 255 ms 33568 KB
50_star_01 276 ms 39556 KB
50_star_02 321 ms 42432 KB
50_star_03 42 ms 6644 KB
60_hand_01 153 ms 23236 KB
60_hand_02 163 ms 22768 KB
60_hand_03 41 ms 6388 KB
60_hand_04 42 ms 6772 KB
60_hand_05 230 ms 31956 KB
60_hand_06 285 ms 37848 KB
60_hand_07 219 ms 30124 KB
60_hand_08 198 ms 28128 KB
60_hand_09 84 ms 12556 KB
60_hand_10 154 ms 22708 KB
60_hand_11 322 ms 41392 KB
60_hand_12 424 ms 51824 KB
60_hand_13 229 ms 31492 KB
60_hand_14 75 ms 11616 KB
60_hand_15 160 ms 23876 KB
60_hand_16 53 ms 8376 KB
60_hand_17 115 ms 17112 KB
60_hand_18 471 ms 55828 KB
60_hand_19 50 ms 8016 KB
60_hand_20 493 ms 58908 KB
60_hand_21 153 ms 22408 KB
60_hand_22 484 ms 58252 KB
60_hand_23 489 ms 57800 KB
60_hand_24 617 ms 72672 KB
60_hand_25 366 ms 45696 KB
60_hand_26 61 ms 9324 KB
60_hand_27 311 ms 40648 KB
60_hand_28 352 ms 45492 KB
60_hand_29 37 ms 6004 KB
60_hand_30 37 ms 5748 KB
70_dense_01 176 ms 25192 KB
70_dense_02 259 ms 31700 KB
70_dense_03 203 ms 27448 KB
70_dense_04 245 ms 31496 KB
70_dense_05 225 ms 30528 KB
70_dense_06 192 ms 26484 KB
70_dense_07 231 ms 29812 KB
70_dense_08 182 ms 25444 KB
70_dense_09 68 ms 10340 KB
70_dense_10 141 ms 20260 KB
90_hand_01 18 ms 3192 KB
90_hand_02 18 ms 3192 KB