CODE THANKS FESTIVAL 2018(Parallel)

Submission #11198711

Source codeソースコード

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
par = [-1] + list(map(int, input().split()))
dists = [0]*(N+1)
child = [[] for _ in range(N+1)]

for i, p in enumerate(par[1:], start=1):
    child[p].append(i)

stack = [0]
while stack:
    v = stack.pop()
    for c in child[v]:
        dists[c] = dists[v]+1
        stack.append(c)

used = [0]*(N+1)
ans = []

for m in range(M-1, -1, -1):
    for i in range(1, N+1):
        if used[i] or K < dists[i]:
            continue

        reachable = 0
        d = []
        stack = [0]

        while stack:
            v = stack.pop()
            for c in child[v]:
                if c == i:
                    reachable = 1
                elif used[c] == 0:
                    d.append(dists[c])
                    stack.append(c)

        d.sort()

        if (
            not reachable
            or sum(d[:m]) > K - dists[i]  # 残りm枚のコインを置ききれない
            or sum(d[-m:]) < K - dists[i]  # 残りm枚のコインでKターン潰せない
        ):
            continue

        ans.append(i)
        used[i] = 1
        K -= dists[i]
        break
    else:
        print(-1)
        exit()

print(*ans)

Submission

Task問題 F - Coins on the tree
User nameユーザ名 testes89
Created time投稿日時
Language言語 PyPy3 (2.4.0)
Status状態 WA
Score得点 0
Source lengthソースコード長 1274 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - s1.txt,s2.txt
All 0 / 400 01.txt,02.txt,03.txt,04.txt,05.txt,06.txt,07.txt,08.txt,09.txt,10.txt,11.txt,12.txt,13.txt,14.txt,15.txt,16.txt,17.txt,18.txt,19.txt,20.txt,21.txt,22.txt,23.txt,24.txt,25.txt,26.txt,27.txt,28.txt,29.txt,30.txt,31.txt,32.txt,33.txt,34.txt,35.txt,36.txt,37.txt,38.txt,39.txt,40.txt,s1.txt,s2.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01.txt AC 192 ms 39920 KB
02.txt WA
03.txt WA
04.txt WA
05.txt WA
06.txt WA
07.txt AC 226 ms 41584 KB
08.txt AC 208 ms 40944 KB
09.txt AC 258 ms 42608 KB
10.txt WA
11.txt WA
12.txt WA
13.txt WA
14.txt WA
15.txt WA
16.txt WA
17.txt WA
18.txt WA
19.txt WA
20.txt WA
21.txt AC 283 ms 42972 KB
22.txt WA
23.txt WA
24.txt WA
25.txt WA
26.txt WA
27.txt WA
28.txt WA
29.txt WA
30.txt WA
31.txt AC 193 ms 40176 KB
32.txt AC 185 ms 39280 KB
33.txt AC 192 ms 40048 KB
34.txt AC 173 ms 38256 KB
35.txt AC 205 ms 41836 KB
36.txt WA
37.txt AC 170 ms 38256 KB
38.txt WA
39.txt AC 172 ms 38256 KB
40.txt WA
s1.txt AC 169 ms 38256 KB
s2.txt AC 171 ms 38256 KB