Contest Duration: ~ (local time) (120 minutes) Back to Home

Submission #10679447

Source Code Expand

Copy
```import sys

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 2020-03-08 21:28:48+0900 C - ThREE maspy Python3 (3.4.3) 600 2001 Byte AC 785 ms 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