結果
問題 | No.2642 Don't cut line! |
ユーザー |
![]() |
提出日時 | 2024-02-19 22:46:13 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,158 bytes |
コンパイル時間 | 239 ms |
コンパイル使用メモリ | 82,032 KB |
実行使用メモリ | 120,464 KB |
最終ジャッジ日時 | 2024-09-29 02:38:40 |
合計ジャッジ時間 | 49,485 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 WA * 2 |
ソースコード
class UnionFind:def __init__(self, n):self._n = nself.parent_or_size = [-1] * ndef merge(self, a, b):assert 0 <= a < self._nassert 0 <= b < self._nx, y = self.leader(a), self.leader(b)if x == y: return xif -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, xself.parent_or_size[x] += self.parent_or_size[y]self.parent_or_size[y] = xreturn xdef same(self, a, b):assert 0 <= a < self._nassert 0 <= b < self._nreturn self.leader(a) == self.leader(b)def leader(self, a):assert 0 <= a < self._nalist=[]while self.parent_or_size[a] >= 0:alist.append(a)a = self.parent_or_size[a]for i in alist:self.parent_or_size[i] = areturn adef size(self, a):assert 0 <= a < self._nreturn -self.parent_or_size[self.leader(a)]def groups(self):leader_buf = [self.leader(i) for i in range(self._n)]result = [[] for _ in range(self._n)]for i in range(self._n): result[leader_buf[i]].append(i)return [r for r in result if r != []]N,K,C=map(int,input().split())edge=[]edge_s=[]edge_w=[]for i in range(K):u,v,w,p=map(int,input().split())u-=1v-=1edge.append((u,v,w,p))edge_s.append((p,i))edge_w.append((w,i))edge_s.sort(key=lambda x:x[0])edge_w.sort(key=lambda x:x[0])for i in range(K-1,0,-1):e1=edge_s[i][1]e0=edge_s[i-1][1]if edge[e1][2]<=edge[e0][2]:edge_s[i-1]=edge_s[i]uf=UnionFind(N)nc=0for _,i in edge_w:u,v,w,p=edge[i]if uf.same(u,v):continueuf.merge(u,v)nc+=wif nc>C:print(-1)exit()d=[0,K]while d[1]-d[0]>1:m=sum(d)//2use=edge_s[m][1]uf=UnionFind(N)nc=0u,v,w,p=edge[use]uf.merge(u,v)nc+=wfor _,i in edge_w:u,v,w,p=edge[i]if uf.same(u,v):continueuf.merge(u,v)nc+=wif nc<=C:d[0]=melse:d[1]=muse=edge_s[d[0]][1]print(edge[use][3])