結果
問題 |
No.1147 土偶Ⅱ
|
ユーザー |
![]() |
提出日時 | 2025-04-09 20:56:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 82 ms / 500 ms |
コード長 | 930 bytes |
コンパイル時間 | 486 ms |
コンパイル使用メモリ | 81,908 KB |
実行使用メモリ | 77,180 KB |
最終ジャッジ日時 | 2025-04-09 20:57:57 |
合計ジャッジ時間 | 2,676 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
import itertools n, m = map(int, input().split()) # Initialize friend matrix friend = [[False] * (n + 1) for _ in range(n + 1)] for _ in range(m): a, b = map(int, input().split()) friend[a][b] = True friend[b][a] = True # Precompute good relationships matrix good = [[False] * (n + 1) for _ in range(n + 1)] for u in range(1, n + 1): for v in range(u + 1, n + 1): if not friend[u][v]: # Check if there's any common friend common = False for k in range(1, n + 1): if k != u and k != v and friend[u][k] and friend[v][k]: common = True break if common: good[u][v] = good[v][u] = True # Count valid triplets count = 0 for trio in itertools.combinations(range(1, n + 1), 3): a, b, c = trio if not good[a][b] and not good[a][c] and not good[b][c]: count += 1 print(count)