結果

問題 No.1023 Cyclic Tour
ユーザー maspymaspy
提出日時 2020-04-10 23:00:00
言語 Python3
(3.11.6 + numpy 1.26.0 + scipy 1.11.3)
結果
AC  
実行時間 833 ms / 2,000 ms
コード長 990 bytes
コンパイル時間 146 ms
コンパイル使用メモリ 10,956 KB
実行使用メモリ 95,744 KB
最終ジャッジ日時 2023-10-14 04:06:31
合計ジャッジ時間 40,638 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 209 ms
42,796 KB
testcase_01 AC 214 ms
43,120 KB
testcase_02 AC 208 ms
42,900 KB
testcase_03 AC 210 ms
43,092 KB
testcase_04 AC 508 ms
70,372 KB
testcase_05 AC 513 ms
71,204 KB
testcase_06 AC 560 ms
74,636 KB
testcase_07 AC 536 ms
71,568 KB
testcase_08 AC 497 ms
68,044 KB
testcase_09 AC 491 ms
66,704 KB
testcase_10 AC 497 ms
66,124 KB
testcase_11 AC 527 ms
68,280 KB
testcase_12 AC 493 ms
67,268 KB
testcase_13 AC 479 ms
66,084 KB
testcase_14 AC 472 ms
65,784 KB
testcase_15 AC 487 ms
67,052 KB
testcase_16 AC 735 ms
91,552 KB
testcase_17 AC 748 ms
92,612 KB
testcase_18 AC 750 ms
94,752 KB
testcase_19 AC 737 ms
92,252 KB
testcase_20 AC 814 ms
93,628 KB
testcase_21 AC 813 ms
94,020 KB
testcase_22 AC 804 ms
92,632 KB
testcase_23 AC 806 ms
94,428 KB
testcase_24 AC 791 ms
95,184 KB
testcase_25 AC 787 ms
93,444 KB
testcase_26 AC 829 ms
94,536 KB
testcase_27 AC 770 ms
92,968 KB
testcase_28 AC 778 ms
94,564 KB
testcase_29 AC 731 ms
93,304 KB
testcase_30 AC 812 ms
95,288 KB
testcase_31 AC 750 ms
91,460 KB
testcase_32 AC 741 ms
92,700 KB
testcase_33 AC 794 ms
95,744 KB
testcase_34 AC 783 ms
92,552 KB
testcase_35 AC 809 ms
94,092 KB
testcase_36 AC 795 ms
93,080 KB
testcase_37 AC 774 ms
92,456 KB
testcase_38 AC 720 ms
91,540 KB
testcase_39 AC 779 ms
93,684 KB
testcase_40 AC 780 ms
93,688 KB
testcase_41 AC 774 ms
93,580 KB
testcase_42 AC 829 ms
94,896 KB
testcase_43 AC 719 ms
91,608 KB
testcase_44 AC 519 ms
72,052 KB
testcase_45 AC 468 ms
67,380 KB
testcase_46 AC 471 ms
67,400 KB
testcase_47 AC 516 ms
70,892 KB
testcase_48 AC 828 ms
95,260 KB
testcase_49 AC 833 ms
95,576 KB
testcase_50 AC 791 ms
95,468 KB
testcase_51 AC 826 ms
95,280 KB
testcase_52 AC 801 ms
95,472 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components
import numpy as np
N, M = map(int, readline().split())
AB1 = []
AB2 = []
m = map(int, read().split())
for a, b, c in zip(m, m, m):
    if c == 1:
        AB1.append((a, b))
    else:
        AB2.append((a, b))

if AB1:
    A1, B1 = zip(*AB1)
else:
    A1, B1 = (), ()
if AB2:
    A2, B2 = zip(*AB2)
else:
    A2, B2 = (), ()

U = A1 + B1 + A2
V = B1 + A1 + B2
G = csr_matrix(([1] * len(U), (U, V)), (N + 1, N + 1))
_, comp = connected_components(G, directed=True, connection='strong')
comp_size = np.bincount(comp)
C = comp.max()
comp = list(comp)

n_edges = [0] * (C + 1)
for a, b in AB1 + AB2:
    ca = comp[a]
    cb = comp[b]
    if ca != cb:
        continue
    n_edges[ca] += 1

bl = any(x <= y for x, y in zip(comp_size, n_edges))
answer = 'Yes' if bl else 'No'
print(answer)
0