結果

問題 No.1293 2種類の道路
コンテスト
ユーザー tcltk
提出日時 2020-11-21 02:43:59
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,071 bytes
コンパイル時間 477 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 46,368 KB
最終ジャッジ日時 2024-07-23 14:21:28
合計ジャッジ時間 4,628 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 7 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
# from typing import *


import io
import sys

# _INPUT = """\
# 4 2 1
# 1 2
# 2 3
# 2 4
# """
# sys.stdin = io.StringIO(_INPUT)


def dfs_car(N, roads_car, pos, seen_car):
    seen_car[pos] = True
    for road in roads_car:
        if road[0] == pos and not seen_car[road[1]]:
            dfs_car(N, roads_car, road[1], seen_car)
        elif road[1] == pos and not seen_car[road[0]]:
            dfs_car(N, roads_car, road[0], seen_car)

def dfs_walk(N, roads_walk, pos, seen_walk):
    seen_walk[pos] = True
    for road in roads_walk:
        if road[0] == pos and not seen_walk[road[1]]:
            dfs_walk(N, roads_walk, road[1], seen_walk)
        elif road[1] == pos and not seen_walk[road[0]]:
            dfs_walk(N, roads_walk, road[0], seen_walk)




# def solve(N: int, D: int, W: int, a: List[int], b: List[int], c: List[int], d: List[int]) -> int:
def solve(N, roads_car, roads_walk):

    count = 0
    seen_car_grand = [False] * N

    for pos in range(N):

        if seen_car_grand[pos]:
            continue

        seen_car = [False] * N
        dfs_car(N, roads_car, pos, seen_car)

        seen_car_walk = [seen for seen in seen_car]

        for pos1 in [i for i, x in enumerate(seen_car) if x]:
            seen_walk = [False] * N
            dfs_walk(N, roads_walk, pos1, seen_walk)
            seen_car_walk = [seen_car_walk[i] or seen_walk[i] for i in range(N)]

        n_car = len([1 for seen in seen_car if seen])
        n_car_walk = len([1 for seen in seen_car_walk if seen])
        count += n_car * (n_car_walk - 1)
        seen_car_grand = [seen_car_grand[i] or seen_car[i] for i in range(N)]

    return count


def main():
    N, D, W = map(int, input().split())
    roads_car = []
    roads_walk = []
    for i in range(D):
        a, b = map(int, input().split())
        roads_car.append((a - 1, b - 1))
    for i in range(W):
        c, d = map(int, input().split())
        roads_walk.append((c - 1, d - 1))
    a1 = solve(N, roads_car, roads_walk)
    print(a1)

if __name__ == '__main__':
    main()
0