E - スプリンクラー, E - SNS のログ

E - スプリンクラー

O(N+M+Q)
無向グラフの問題です。
隣接行列を使っています。

python

import math
import heapq
import itertools
from functools import reduce

# main
def main():
    N, M, Q = list(map(int, input().split()))
    graph = []

    for y in range(0, N):
        row = []
        for x in range(0, N):
            row.append(False)
        graph.append(row)

    for _ in range(0, M):
        u, v = list(map(int, input().split()))
        u = u - 1
        v = v - 1
        graph[u][v] = True
        graph[v][u] = True

    C = list(map(int, input().split()))

    for _ in range(0, Q):
        q = list(map(int, input().split()))

        if q[0] == 1:
            x = q[1] - 1 
            print(C[x])

            for i in range(0, N):
                if graph[x][i]:
                    C[i] = C[x]

        if q[0] == 2:
            x = q[1] - 1 
            y = q[2]
            print(C[x])
            C[x] = y

# エントリポイント
if __name__ == '__main__':
    main()

メモリの制約で隣接行列を使用できない場合、隣接リストを使用します。

python

import math
import heapq
import itertools
from functools import reduce

# main
def main():
    N, M, Q = list(map(int, input().split()))
    graph = []

    for y in range(0, N):
        row = []
        graph.append(row)

    for _ in range(0, M):
        u, v = list(map(int, input().split()))
        u = u - 1
        v = v - 1
        graph[u].append(v)
        graph[v].append(u)

    C = list(map(int, input().split()))

    for _ in range(0, Q):
        q = list(map(int, input().split()))

        if q[0] == 1:
            x = q[1] - 1 
            print(C[x])

            for i in graph[x]:
                C[i] = C[x]

        if q[0] == 2:
            x = q[1] - 1 
            y = q[2]
            print(C[x])
            C[x] = y

# エントリポイント
if __name__ == '__main__':
    main()

E - SNS のログ

O(N)
有向グラフの問題です。

python

import math
import heapq
import itertools
from functools import reduce

# main
def main():
    N, Q = list(map(int, input().split()))
    graph = []

    for y in range(0, N):
        row = []
        for x in range(0, N):
            row.append(False)
        graph.append(row)

    for _ in range(0, Q):
        s = list(map(int, input().split()))

        if s[0] == 1:
            graph[s[1]-1][s[2]-1] = True
        elif s[0] == 2:
            for i in range(0, N):
                if graph[i][s[1]-1]:
                    graph[s[1]-1][i] = True
        elif s[0] == 3:
            to_follow = []
            for i in range(0, N):
                if graph[s[1]-1][i]:
                    for j in range(0, N):
                        if graph[i][j] and s[1]-1 != j:
                            to_follow.append(j)
            for i in to_follow:
                graph[s[1]-1][i] = True

    for i in range(0, N):
        row = ""
        for j in range(0, N):
            if graph[i][j]:
                row += "Y"
            else:
                row += "N"
        print(row)

# エントリポイント
if __name__ == '__main__':
    main()