Submission #62309641

---

Source Code Expand

def query_1(x, y, pigeons_positions, nest_pigeons, num_of_crowded_nests):
    current_nest_id = pigeons_positions[x]

    # 鳩を移動させる
    pigeons_positions[x] = y

    # 巣にいる鳩の数を更新する
    nest_pigeons[y] += 1
    nest_pigeons[current_nest_id] -= 1

    # 巣xの鳩の数が負の場合はおかしい
    assert nest_pigeons[current_nest_id] >= 0

    # 複数羽いる鳩の巣の数を更新する
    # 巣yは必ず増えている。2になったらnum_of_crowded_nestsを増やす
    # print(f'num_of_crowded_nests: {num_of_crowded_nests}, nest_pigeons[y]: {nest_pigeons[y]}')
    if nest_pigeons[y] == 2:
        num_of_crowded_nests += 1
    # 巣xは必ず減っている。1になったらnum_of_crowded_nestを減らす
    # print(f'num_of_crowded_nests: {num_of_crowded_nests}, nest_pigeons[current_nest_id]: {nest_pigeons[current_nest_id]}')
    if nest_pigeons[current_nest_id] == 1:
        num_of_crowded_nests -= 1
    return num_of_crowded_nests


def query_2(nest_pigeons, num_of_crowded_nest):
    # print(nest_pigeons)
    print(num_of_crowded_nest)


def main(N, Q):
    # 各鳩が今どの巣にいるか
    pigeons_positions = {}
    # 各巣にいる鳩の数
    nest_pigeons = {}
    # 巣の数
    num_of_crowded_nests = 0
    for i in range(1, N + 1):
        pigeons_positions[i] = i
        nest_pigeons[i] = 1

    for _ in range(Q):
        queries = input().split()
        if len(queries) == 3:
            _, x, y = queries
            x = int(x)
            y = int(y)
            num_of_crowded_nests = query_1(
                x, y, pigeons_positions, nest_pigeons, num_of_crowded_nests
            )
            # print(f'check side effect: {num_of_crowded_nests}')
        else:
            query_2(nest_pigeons, num_of_crowded_nests)


N, Q = map(int, input().split())
main(N, Q)

Submission Info

Judge Result