結果

問題 No.2642 Don't cut line!
ユーザー timi
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

N,K,C=map(int,input().split())
par=[i for i in range(N)]
rank=[0]*(N)
friend=[0]*N
block=[0]*N
size=[1]*N
def find(x):
if par[x]==x:
return x
else:
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:
return
if rank[x]>rank[y]:
par[y]=x
size[x]+=size[y]
else:
par[x]=y
size[y]+=size[x]
if rank[x]==rank[y]:
rank[y]+=1
A=[]
for i in range(K):
u,v,w,p=map(int,input().split())
u-=1;v-=1
A.append((w,u,v,p))
A=sorted(A)
B=[];AA=[]
cost=0;pp=0
for w,u,v,p in A:
if not same(u,v):
union(u,v)
AA.append((u,v,w))
pp=max(p,pp)
cost+=w
else:
B.append((p,u,v,w))
#print(cost,pp)
if cost>C:
print(-1)
exit()
from collections import deque
class HLD():
def __init__(self, edge_list, op, e):
self.edge_list = edge_list
self.op = op
self.e = e
self.__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] = par
for npos, weight in self.Graph[pos]:
if npos == par:
continue
dfs_stack.append((pos, npos))
back_stack.append((pos, npos))
self.to_parent_weight[npos] = weight
heaviest_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]: vheavy-pathtop()
self.top_dist = [(-1, -1)] * self.N
self.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-path
if 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-edgeheavy-path
else:
que.append((npos, pos, npos, 0))
self.heavy_depth[npos] = self.heavy_depth[pos] + 1
weight_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, a
self.to_parent_weight[b] = new_weight
b_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.e
while 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))
break
if 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 -= 1
else:
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 -= 1
return ans
# shakayami
class segtree():
n = 1
size = 1
log = 2
d = [0]
op = None
e = 10 ** 15
def __init__(self, V, OP, E):
self.n = len(V)
self.op = OP
self.e = E
self.log = (self.n - 1).bit_length()
self.size = 1 << self.log
self.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.n
p += self.size
self.d[p] = x
for i in range(1, self.log + 1):
self.update(p >> i)
def get(self, p):
assert 0 <= p and p < self.n
return self.d[p + self.size]
def prod(self, l, r):
assert 0 <= l and l <= r and r <= self.n
sml = self.e
smr = self.e
l += self.size
r += self.size
while (l < r):
if (l & 1):
sml = self.op(sml, self.d[l])
l += 1
if (r & 1):
smr = self.op(self.d[r - 1], smr)
r -= 1
l >>= 1
r >>= 1
return self.op(sml, smr)
def all_prod(self):
return self.d[1]
def max_right(self, l, f):
assert 0 <= l and l <= self.n
assert f(self.e)
if l == self.n:
return self.n
l += self.size
sm = self.e
while (1):
while (l % 2 == 0):
l >>= 1
if not (f(self.op(sm, self.d[l]))):
while (l < self.size):
l = 2 * l
if f(self.op(sm, self.d[l])):
sm = self.op(sm, self.d[l])
l += 1
return l - self.size
sm = self.op(sm, self.d[l])
l += 1
if (l & -l) == l:
break
return self.n
def min_left(self, r, f):
assert 0 <= r and r < self.n
assert f(self.e)
if r == 0:
return 0
r += self.size
sm = self.e
while (1):
r -= 1
while (r > 1 & (r % 2)):
r >>= 1
if 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 -= 1
return r + 1 - self.size
sm = self.op(self.d[r], sm)
if (r & -r) == r:
break
return 0
def 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 = AA
def mi(num1, num2):
return min(num1,num2)
hld = HLD(edge_list,mi,10**15)
ans=pp
for p,u,v,w in B:
co=cost+w-hld.solve(u,v)
if co<=C:
ans=max(ans,max(pp,p))
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0