結果
問題 | No.1817 Reversed Edges |
ユーザー | tktk_snsn |
提出日時 | 2022-05-13 12:39:03 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 548 ms / 2,000 ms |
コード長 | 675 bytes |
コンパイル時間 | 187 ms |
コンパイル使用メモリ | 10,948 KB |
実行使用メモリ | 32,724 KB |
最終ジャッジ日時 | 2023-09-28 15:35:09 |
合計ジャッジ時間 | 10,907 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 16 ms
7,764 KB |
testcase_01 | AC | 16 ms
7,840 KB |
testcase_02 | AC | 16 ms
7,760 KB |
testcase_03 | AC | 16 ms
7,760 KB |
testcase_04 | AC | 16 ms
7,884 KB |
testcase_05 | AC | 15 ms
7,840 KB |
testcase_06 | AC | 16 ms
7,764 KB |
testcase_07 | AC | 447 ms
30,328 KB |
testcase_08 | AC | 200 ms
18,632 KB |
testcase_09 | AC | 422 ms
29,228 KB |
testcase_10 | AC | 231 ms
20,096 KB |
testcase_11 | AC | 317 ms
23,412 KB |
testcase_12 | AC | 548 ms
32,536 KB |
testcase_13 | AC | 548 ms
32,572 KB |
testcase_14 | AC | 548 ms
32,632 KB |
testcase_15 | AC | 527 ms
32,724 KB |
testcase_16 | AC | 522 ms
32,640 KB |
testcase_17 | AC | 505 ms
32,520 KB |
testcase_18 | AC | 512 ms
32,528 KB |
testcase_19 | AC | 513 ms
32,548 KB |
testcase_20 | AC | 493 ms
32,652 KB |
testcase_21 | AC | 501 ms
32,692 KB |
testcase_22 | AC | 324 ms
27,060 KB |
testcase_23 | AC | 324 ms
27,088 KB |
testcase_24 | AC | 333 ms
32,496 KB |
ソースコード
import sys input = sys.stdin.buffer.readline sys.setrecursionlimit(10 ** 7) N = int(input()) G = [[] for _ in range(N)] for _ in range(N - 1): a, b = map(int, input().split()) a -= 1 b -= 1 G[a].append(b) G[b].append(a) par = [-1] * N topo = [] que = [0] while que: s = que.pop() topo.append(s) for t in G[s]: if t == par[s]: continue par[t] = s que.append(t) dp = [0] * N for s in topo[::-1][:-1]: p = par[s] dp[p] += dp[s] if p > s: dp[p] += 1 for s in topo[1:]: p = par[s] dp[s] = dp[p] if p > s: dp[s] -= 1 else: dp[s] += 1 print(*dp, sep="\n")