結果
問題 | No.2642 Don't cut line! |
ユーザー |
![]() |
提出日時 | 2024-02-23 15:01:51 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,253 bytes |
コンパイル時間 | 309 ms |
コンパイル使用メモリ | 82,384 KB |
実行使用メモリ | 155,844 KB |
最終ジャッジ日時 | 2024-09-29 05:09:16 |
合計ジャッジ時間 | 29,599 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 WA * 1 |
ソースコード
N,K,C=map(int,input().split())par=[i for i in range(N)]rank=[0]*(N)friend=[0]*Nblock=[0]*Nsize=[1]*Ndef find(x):if par[x]==x:return xelse:par[x]=find(par[x])return par[x]#同じ集合か判定def same(x,y):return find(x)==find(y)def union(x,y):x=find(x)y=find(y)if x==y:returnif rank[x]>rank[y]:par[y]=xsize[x]+=size[y]else:par[x]=ysize[y]+=size[x]if rank[x]==rank[y]:rank[y]+=1A=[]for i in range(K):u,v,w,p=map(int,input().split())u-=1;v-=1A.append((w,u,v,p))A=sorted(A)B=[];AA=[]cost=0;pp=0for w,u,v,p in A:if not same(u,v):union(u,v)AA.append((u,v,w))pp=max(p,pp)cost+=welse:B.append((p,u,v,w))#print(cost,pp)if cost>C:print(-1)exit()from collections import dequeclass HLD():def __init__(self, edge_list, op, e):self.edge_list = edge_listself.op = opself.e = eself.__build()def __build(self):self.N = len(self.edge_list) + 1 # 全ノードの数self.Graph = [[] for _ in range(self.N)] # 無向グラフを構築for n1, n2, weight in self.edge_list:self.Graph[n1].append([n2, weight])self.Graph[n2].append([n1, weight])self.siz = [1] * self.N # 部分木のサイズself.parent = [-1] * self.N # 親ノード番号self.to_parent_weight = [-1] * self.N # 親ノードを結ぶ辺の重みdfs_stack = [(-1, 0)]back_stack = []while dfs_stack:par, pos = dfs_stack.pop()self.parent[pos] = parfor npos, weight in self.Graph[pos]:if npos == par:continuedfs_stack.append((pos, npos))back_stack.append((pos, npos))self.to_parent_weight[npos] = weightheaviest_child = [(-1, 0)] * self.N # (ノード番号, 部分木サイズ)を格納while back_stack:par, pos = back_stack.pop()self.siz[par] += self.siz[pos]if heaviest_child[par][1] < self.siz[pos]:heaviest_child[par] = (pos, self.siz[pos])# self.top_dist[v]: ノードvの属するheavy-pathのtopと、そこまでの最短パス(通る辺の数)self.top_dist = [(-1, -1)] * self.Nself.top_dist[0] = (0, 0)que = deque()que.append((0, -1, 0, 0)) # (pos, par, top, dist)を格納self.heavy_depth = [0] * self.N # light-edge を通った回数weight_list_dict = dict()weight_list_dict[0] = []while que:pos, par, top, dist = que.popleft()heaviest_node = heaviest_child[pos][0]for npos, weight in self.Graph[pos]:if npos == par:continue# おなじheavy-pathif npos == heaviest_node:que.append((npos, pos, top, dist + 1))self.heavy_depth[npos] = self.heavy_depth[pos]weight_list_dict[top].append(weight)self.top_dist[npos] = (top, dist + 1)# light-edgeを通り、新しいheavy-pathを生成else:que.append((npos, pos, npos, 0))self.heavy_depth[npos] = self.heavy_depth[pos] + 1weight_list_dict[npos] = []self.top_dist[npos] = (npos, 0)self.weight_st_dict = dict()for top, weight_list in weight_list_dict.items():self.weight_st_dict[top] = segtree(weight_list_dict[top], self.op,self.e)def weight_set(self, edge_number, new_weight):a, b, old_weight = self.edge_list[edge_number]if self.parent[a] == b:a, b = b, aself.to_parent_weight[b] = new_weightb_top, b_dist = self.top_dist[b]if b_dist > 0:self.weight_st_dict[b_top].set(b_dist - 1, new_weight)def solve(self, n1, n2):hd1 = self.heavy_depth[n1]top1, dist1 = self.top_dist[n1]hd2 = self.heavy_depth[n2]top2, dist2 = self.top_dist[n2]ans = self.ewhile True:if top1 == top2:if dist1 < dist2:ans = self.op(ans,self.weight_st_dict[top1].prod(dist1, dist2))elif dist2 < dist1:ans = self.op(ans,self.weight_st_dict[top1].prod(dist2, dist1))breakif hd1 < hd2:ans = self.op(ans, self.weight_st_dict[top2].prod(0, dist2))ans = self.op(ans, self.to_parent_weight[top2])n2 = self.parent[top2]top2, dist2 = self.top_dist[n2]hd2 -= 1else:ans = self.op(ans, self.weight_st_dict[top1].prod(0, dist1))ans = self.op(ans, self.to_parent_weight[top1])n1 = self.parent[top1]top1, dist1 = self.top_dist[n1]hd1 -= 1return ans# shakayamiさん作のセグメントツリーclass segtree():n = 1size = 1log = 2d = [0]op = Nonee = 10 ** 15def __init__(self, V, OP, E):self.n = len(V)self.op = OPself.e = Eself.log = (self.n - 1).bit_length()self.size = 1 << self.logself.d = [E for i in range(2 * self.size)]for i in range(self.n):self.d[self.size + i] = V[i]for i in range(self.size - 1, 0, -1):self.update(i)def set(self, p, x):assert 0 <= p and p < self.np += self.sizeself.d[p] = xfor i in range(1, self.log + 1):self.update(p >> i)def get(self, p):assert 0 <= p and p < self.nreturn self.d[p + self.size]def prod(self, l, r):assert 0 <= l and l <= r and r <= self.nsml = self.esmr = self.el += self.sizer += self.sizewhile (l < r):if (l & 1):sml = self.op(sml, self.d[l])l += 1if (r & 1):smr = self.op(self.d[r - 1], smr)r -= 1l >>= 1r >>= 1return self.op(sml, smr)def all_prod(self):return self.d[1]def max_right(self, l, f):assert 0 <= l and l <= self.nassert f(self.e)if l == self.n:return self.nl += self.sizesm = self.ewhile (1):while (l % 2 == 0):l >>= 1if not (f(self.op(sm, self.d[l]))):while (l < self.size):l = 2 * lif f(self.op(sm, self.d[l])):sm = self.op(sm, self.d[l])l += 1return l - self.sizesm = self.op(sm, self.d[l])l += 1if (l & -l) == l:breakreturn self.ndef min_left(self, r, f):assert 0 <= r and r < self.nassert f(self.e)if r == 0:return 0r += self.sizesm = self.ewhile (1):r -= 1while (r > 1 & (r % 2)):r >>= 1if not (f(self.op(self.d[r], sm))):while (r < self.size):r = (2 * r + 1)if f(self.op(self.d[r], sm)):sm = self.op(self.d[r], sm)r -= 1return r + 1 - self.sizesm = self.op(self.d[r], sm)if (r & -r) == r:breakreturn 0def update(self, k):self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])def __str__(self):return str([self.get(i) for i in range(self.n)])#print(B,AA)edge_list = AAdef mi(num1, num2):return min(num1,num2)hld = HLD(edge_list,mi,10**15)ans=ppfor p,u,v,w in B:co=cost+w-hld.solve(u,v)if co<=C:ans=max(ans,max(pp,p))print(ans)