結果
問題 |
No.1789 Tree Growing
|
ユーザー |
![]() |
提出日時 | 2025-06-12 14:48:42 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 937 bytes |
コンパイル時間 | 191 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 52,736 KB |
最終ジャッジ日時 | 2025-06-12 14:52:18 |
合計ジャッジ時間 | 6,105 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 WA * 34 |
ソースコード
def count_leaves(adj, num_nodes): leaves = 0 for i in range(1, num_nodes + 1): if len(adj[i]) == 1: leaves += 1 return leaves def main(): import sys input = sys.stdin.read().split() ptr = 0 K = int(input[ptr]) ptr += 1 adj_t1 = [[] for _ in range(K + 1)] for _ in range(K - 1): a = int(input[ptr]) b = int(input[ptr + 1]) ptr += 2 adj_t1[a].append(b) adj_t1[b].append(a) L_t1 = count_leaves(adj_t1, K) N = int(input[ptr]) ptr += 1 adj_t2 = [[] for _ in range(N + 1)] for _ in range(N - 1): c = int(input[ptr]) d = int(input[ptr + 1]) ptr += 2 adj_t2[c].append(d) adj_t2[d].append(c) L_t2 = count_leaves(adj_t2, N) if L_t2 < L_t1: print(-1) else: max_red = (N - 1) - (L_t2 - L_t1) print(max_red) if __name__ == "__main__": main()