結果

問題 No.488 四角関係
ユーザー kjnhokjnho
提出日時 2017-02-24 23:22:48
言語 Python3
(3.11.6 + numpy 1.26.0 + scipy 1.11.3)
結果
AC  
実行時間 736 ms / 5,000 ms
コード長 937 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 10,956 KB
実行使用メモリ 8,384 KB
最終ジャッジ日時 2023-08-30 23:50:00
合計ジャッジ時間 4,229 ms
ジャッジサーバーID
(参考情報)
judge11 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 177 ms
8,260 KB
testcase_01 AC 132 ms
8,236 KB
testcase_02 AC 170 ms
8,324 KB
testcase_03 AC 67 ms
8,316 KB
testcase_04 AC 99 ms
8,220 KB
testcase_05 AC 220 ms
8,200 KB
testcase_06 AC 344 ms
8,272 KB
testcase_07 AC 425 ms
8,280 KB
testcase_08 AC 736 ms
8,276 KB
testcase_09 AC 16 ms
8,364 KB
testcase_10 AC 49 ms
8,304 KB
testcase_11 AC 17 ms
8,200 KB
testcase_12 AC 34 ms
8,188 KB
testcase_13 AC 44 ms
8,224 KB
testcase_14 AC 21 ms
8,384 KB
testcase_15 AC 17 ms
8,288 KB
testcase_16 AC 16 ms
8,264 KB
testcase_17 AC 16 ms
8,360 KB
testcase_18 AC 16 ms
8,384 KB
testcase_19 AC 17 ms
8,228 KB
testcase_20 AC 16 ms
8,288 KB
testcase_21 AC 16 ms
8,220 KB
testcase_22 AC 16 ms
8,196 KB
testcase_23 AC 17 ms
8,244 KB
testcase_24 AC 16 ms
8,176 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import itertools
def main():
    global mapping
    N, M = map(int, input().split())

    mapping = [[False]*N for n in range(N)]
    for m in range(M):
        a, b = map(int, input().split())
        mapping[a][b] = True
        mapping[b][a] = True

    # print(mapping)

    count = 0
    for c in itertools.combinations(range(N), 4):
        if check(c):
            count += 1

    print(count)

def check(c):
    for p in itertools.permutations([c[1],c[2],c[3]]):
        if connected(c[0], p[0]) and connected(p[0], p[1]) and connected(p[1], p[2]) and connected(p[2], c[0]):
            if (not connected(c[0], p[1])) and (not connected(p[0],p[2])):
                return True
    return False


def connected(x,y):
    if mapping[x][y] or mapping[y][x]:
        return True
    else:
        return False


if __name__ == "__main__":  # {{{
    try:
        import test
        test.test()
    except:
        main()  # }}}

 
0