#1186582 (PyPy3) No.3756 Udon Network

• 問題: No.3756 Udon Network
• ユーザー: tsunamayo123
• 提出日時: 2026-09-12 14:01:21
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: AC
• 実行時間: 1,129 ms / 2,000 ms
• コード長: 3,331 bytes
• コンパイル時間: 65 ms
• コンパイル使用メモリ: 82,104 KB
• 実行使用メモリ: 248,500 KB
• 最終ジャッジ日時: 2026-10-09 17:44:02
• 合計ジャッジ時間: 39,906 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge5_0

サブタスク	配点	結果
Example	0 %	AC * 8
Subtask $1$	2 %	AC * 15
Subtask $2$	4 %	AC * 22
Subtask $3$	8 %	AC * 9
Subtask $4$	16 %	AC * 10
Subtask $5$	32 %	AC * 10
Subtask $6$	38 %	AC * 53
合計	4 * 100% = 400 点

ソースコード

# 部分点6(満点)
# Kruskal Reconstruction Tree + Euler Tour + BIT(fenwick tree) + Binary lifting

import sys
from atcoder.dsu import DSU
from atcoder.fenwicktree import FenwickTree

input = sys.stdin.readline

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

A = list(map(int, input().split()))
for i in range(N):
    A[i] -= 1

B = []

U = [0] * M
V = [0] * M
W = [0] * M

for j in range(M):
    U[j], V[j], W[j] = map(int, input().split())
    U[j] -= 1
    V[j] -= 1

    B.append((W[j], j))

B.sort()

child = [(-1, -1) for _ in range(2 * N)]
parent = [-1] * (2 * N)
weight = [0] * (2 * N)

UF = DSU(N)

comp = [0] * N
for i in range(N):
    comp[i] = i

nodes = N

# Kruskal Reconstruction Treeを構築してる
for w, j in B:
    a = UF.leader(U[j])
    b = UF.leader(V[j])

    if a == b:
        continue

    x = comp[a]
    y = comp[b]
    z = nodes
    nodes += 1

    # 新しくwの頂点を作って、子にx,yを持たせる
    weight[z] = w
    child[z] = (x, y)

    parent[x] = parent[y] = z

    root = UF.merge(a, b)
    comp[root] = z

root = comp[UF.leader(0)]

# DFSでEuler Tourを構築
st = []
st.append(root)

order = []

while st:
    i = st.pop()

    if i < N:
        order.append(i)
    else:
        st.append(child[i][0])
        st.append(child[i][1])

L = [0] * nodes
R = [0] * nodes

for i in range(N):
    v = order[i]
    L[v] = R[v] = i  # 必ず葉なのでLとRは同じ

# rootに近づくほど頂点番号が大きくなってるので、小さい順に処理する
for i in range(N, nodes):
    a, b = child[i]
    L[i] = min(L[a], L[b])  # 頂点に入っていくとき
    R[i] = max(R[a], R[b])  # 頂点から出ていくとき

# BIT(fenwick tree)を用いて、ある頂点におけるEuler Tourの区間内の種類数を求める
last = [-1] * N
cnt = [0] * nodes

fw = FenwickTree(N)

# R[i]が小さい順から見る -> 頂点から出ていく時間が早い順
r = [[] for _ in range(N)]

for i in range(nodes):
    r[R[i]].append(i)

for i in range(N):
    v = order[i]
    c = A[v]

    # 種類数をsumで求めるために系列cの+1を移動する
    if last[c] != -1:
        fw.add(last[c], -1)

    fw.add(i, 1)
    last[c] = i  # 更新し忘れてた

    for u in r[i]:
        cnt[u] = fw.sum(L[u], R[u] + 1)

# s_kのcnt[v]>=c_kとなる祖先vがあるとき、weight[v]が答え
# Binary lifting(ダブリング)を使ってvを求める
siz = 1

while (1 << siz) <= nodes:
    siz += 1

up = [[-1] * nodes for _ in range(siz)]

# vの2^0個上の祖先はvの親
for v in range(nodes):
    up[0][v] = parent[v]

for j in range(1, siz):
    for v in range(nodes):
        if up[j - 1][v] != -1:
            # ここダブリング
            up[j][v] = up[j - 1][up[j - 1][v]]

ans = []

for k in range(Q):
    s, c = map(int, input().split())
    s -= 1

    if cnt[root] < c:
        # KRTの根が最大値を取る
        ans.append("-1")

    elif cnt[s] >= c:
        ans.append("0")

    else:
        v = s

        for j in range(siz - 1, -1, -1):
            x = up[j][v]

            # cnt[x]==cとなる直前まで祖先を登る(cntは単調増加)
            if x != -1 and cnt[x] < c:
                v = x

        # KRTで追加したw_jを持っている点
        x = up[0][v]
        ans.append(str(weight[x]))

print("\n".join(ans))