結果
問題 | No.2642 Don't cut line! |
ユーザー |
|
提出日時 | 2024-02-19 22:43:52 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,092 bytes |
コンパイル時間 | 256 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 339,012 KB |
最終ジャッジ日時 | 2024-09-29 03:36:53 |
合計ジャッジ時間 | 19,504 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 WA * 1 |
ソースコード
import syssys.setrecursionlimit(500000)def input():return sys.stdin.readline()[:-1]from collections import dequeclass UnionFind():def __init__(self,size):self.table = [-1 for _ in range(size)]self.member_num = [1 for _ in range(size)]#representative#O(a(N))def find(self,x):Q = deque()while self.table[x] >= 0:Q.append(x)x = self.table[x]while len(Q)>0:y = Q.pop()self.table[y] = xreturn xdef union(self,x,y):s1 = self.find(x)s2 = self.find(y)m1=self.member_num[s1]m2=self.member_num[s2]if s1 != s2:if m1 != m2:if m1 < m2:self.table[s1] = s2self.member_num[s2]=m1+m2return [m1,m2]else:self.table[s2] = s1self.member_num[s1]=m1+m2return [m1,m2]else:self.table[s1] = -1self.table[s2] = s1self.member_num[s1] = m1+m2return [m1,m2]return [0,0]N,K,C = list(map(int,input().split()))edges = []for i in range(K):u,v,w,p = list(map(int,input().split()))u -= 1v -= 1edges.append((u,v,w,p))edges.sort(key=lambda x:x[2])ans = 0UF = UnionFind(N)ret = 0count = 0e_list = [[] for i in range(N)]rest = []for u,v,w,p in edges:if UF.find(u) != UF.find(v):UF.union(u,v)e_list[u].append((v, w))e_list[v].append((u, w))ret += wcount += 1ans = max(ans, p)else:rest.append((u,v,w,p))if ret > C:print(-1)else:par = [-1]*Ndepth = [0]*Nmn = [10**9]*Ndef dfs(v):for v1, w in e_list[v]:if v1 != par[v]:par[v1] = vmn[v1] = wdepth[v1] = depth[v] + 1dfs(v1)dfs(0)DP1 = [[0]*N for i in range(20)]DP2 = [[0]*N for i in range(20)]for i in range(N):DP1[0][i] = par[i]DP2[0][i] = mn[i]for i in range(19):for j in range(N):DP1[i+1][j] = DP1[i][DP1[i][j]]DP2[i+1][j] = min(DP2[i][j], DP2[i][DP1[i][j]])def lca_min(u,v):ret = 10**9if depth[u] > depth[v]:u,v = v,ud1 = depth[u]d2 = depth[v]diff = d2 - d1b = 1count = 0while b < 2*diff:if (b&diff) > 0:v = DP1[count][v]ret = min(DP2[count][v], ret)b *= 2count += 1l = 0for i in range(19, -1, -1):if DP1[i][u] != DP1[i][v]:ret = min(DP2[i][u], DP2[i][v], ret)u = DP1[i][u]v = DP1[i][v]ret = min(DP2[0][u], DP2[0][v], ret)return retfor u,v,w,p in rest:if ret + w - lca_min(u,v) <= C:ans = max(p, ans)print(ans)