結果

問題 No.3071 Double Speedrun
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:41:21
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,488 bytes
コンパイル時間 335 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 68,232 KB
最終ジャッジ日時 2025-06-12 19:41:24
合計ジャッジ時間 2,315 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from collections import defaultdict, deque

def main():
    input = sys.stdin.read().split()
    ptr = 0

    L = int(input[ptr]); ptr +=1
    R = int(input[ptr]); ptr +=1
    M = int(input[ptr]); ptr +=1

    edges = []
    deg = defaultdict(int)
    for _ in range(M):
        a = int(input[ptr]); ptr +=1
        b = int(input[ptr]); ptr +=1
        edges.append((a, b))
        deg[a] +=1
        deg[b + L] +=1  # V2的顶点编号从L开始

    # 计算所有顶点的度数
    all_deg = []
    for v in range(L + R):
        all_deg.append(deg[v])
    
    # 计算GCD
    def compute_gcd(list_numbers):
        from functools import reduce
        return reduce(math.gcd, list_numbers)
    
    K = compute_gcd(all_deg)
    s = {}
    for v in range(L + R):
        s[v] = deg[v] // K

    # 初始化颜色计数器
    color_count = defaultdict(lambda: defaultdict(int))
    for v in range(L + R):
        for c in range(K):
            color_count[v][c] = 0

    color_assignment = [0] * M

    # 将边分配到颜色中
    for idx, (a, b) in enumerate(edges):
        b_v2 = b + L
        for c in range(K):
            if color_count[a][c] < s[a] and color_count[b_v2][c] < s[b_v2]:
                color_assignment[idx] = c
                color_count[a][c] += 1
                color_count[b_v2][c] += 1
                break

    # 输出结果
    print(K)
    print('\n'.join(map(str, color_assignment)))

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