#1152946 (PyPy3) No.3568 Range Restriction

• 問題: No.3568 Range Restriction
• ユーザー: 👑 to-omer
• 提出日時: 2026-03-20 20:31:28
• 言語: PyPy3 (7.3.17)
• 結果: TLE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 4,246 bytes
• コンパイル時間: 328 ms
• コンパイル使用メモリ: 84,864 KB
• 実行使用メモリ: 325,376 KB
• 最終ジャッジ日時: 2026-06-06 01:37:55
• 合計ジャッジ時間: 19,795 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
sample	AC * 1
other	AC * 19 TLE * 1

ソースコード

import heapq
import sys
from collections import deque


def solve() -> None:
    it = iter(map(int, sys.stdin.buffer.read().split()))
    t = next(it)
    out = []

    for _ in range(t):
        n = next(it)
        m = next(it)

        constraints = []

        self_groups = [[] for _ in range(n)]

        pair_to_gid = {}
        g_u = []
        g_v = []
        g_items = []

        for _ in range(m):
            x = next(it) - 1
            y = next(it) - 1
            z = next(it) - 1
            v = next(it)
            l = next(it)
            r = next(it)
            constraints.append((x, y, z, v, l, r))

            if x == y:
                self_groups[x].append((v, z, l))
            else:
                if x > y:
                    x, y = y, x
                key = (x, y)
                gid = pair_to_gid.get(key)
                if gid is None:
                    gid = len(g_u)
                    pair_to_gid[key] = gid
                    g_u.append(x)
                    g_v.append(y)
                    g_items.append([])
                g_items[gid].append((v, z, l))

        deg = [0] * n
        for x, y in pair_to_gid:
            deg[x] += 1
            deg[y] += 1

        g = len(g_u)

        tail = [0] * g
        head = [0] * g
        out_groups = [[] for _ in range(n)]

        for gid in range(g):
            u = g_u[gid]
            v = g_v[gid]
            if deg[u] < deg[v] or (deg[u] == deg[v] and u < v):
                t0, h0 = u, v
            else:
                t0, h0 = v, u
            tail[gid] = t0
            head[gid] = h0
            out_groups[t0].append(gid)
            g_items[gid].sort(key=lambda x: x[0])

        for u in range(n):
            self_groups[u].sort(key=lambda x: x[0])

        ptr = [0] * g
        self_ptr = [0] * n

        heaps = [[] for _ in range(n)]

        a = [0] * n

        q = deque(range(n))
        inq = [True] * n

        while q:
            u = q.popleft()
            inq[u] = False

            arr = self_groups[u]
            p = self_ptr[u]
            s2 = a[u] * 2
            while p < len(arr) and arr[p][0] <= s2:
                _, z, l = arr[p]
                if a[z] < l:
                    a[z] = l
                    if not inq[z]:
                        inq[z] = True
                        q.append(z)
                p += 1
            self_ptr[u] = p

            for gid in out_groups[u]:
                arr = g_items[gid]
                p = ptr[gid]
                s = a[g_u[gid]] + a[g_v[gid]]
                while p < len(arr) and arr[p][0] <= s:
                    _, z, l = arr[p]
                    if a[z] < l:
                        a[z] = l
                        if not inq[z]:
                            inq[z] = True
                            q.append(z)
                    p += 1
                ptr[gid] = p

                if p < len(arr):
                    need = arr[p][0] - a[tail[gid]]
                    heapq.heappush(heaps[head[gid]], (need, gid, p))

            h = heaps[u]
            while h and h[0][0] <= a[u]:
                need, gid, p0 = heapq.heappop(h)

                if p0 != ptr[gid]:
                    continue
                arr = g_items[gid]
                if need != arr[p0][0] - a[tail[gid]]:
                    continue

                p = p0
                s = a[g_u[gid]] + a[g_v[gid]]
                while p < len(arr) and arr[p][0] <= s:
                    _, z, l = arr[p]
                    if a[z] < l:
                        a[z] = l
                        if not inq[z]:
                            inq[z] = True
                            q.append(z)
                    p += 1
                ptr[gid] = p

                if p < len(arr):
                    new_need = arr[p][0] - a[tail[gid]]
                    heapq.heappush(h, (new_need, gid, p))

        ok = True
        for x, y, z, v, l, r in constraints:
            if a[x] + a[y] >= v and not (l <= a[z] <= r):
                ok = False
                break

        if ok:
            out.append(" ".join(map(str, a)))
        else:
            out.append("-1")

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()