結果
| 問題 | No.2642 Don't cut line! |
| ユーザー |
👑 |
| 提出日時 | 2024-02-23 15:01:51 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,253 bytes |
| コンパイル時間 | 845 ms |
| コンパイル使用メモリ | 81,828 KB |
| 実行使用メモリ | 155,964 KB |
| 最終ジャッジ日時 | 2024-02-23 15:02:24 |
| 合計ジャッジ時間 | 31,988 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge16 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | AC | 1,087 ms
155,964 KB |
| testcase_02 | AC | 1,072 ms
153,936 KB |
| testcase_03 | AC | 1,017 ms
153,576 KB |
| testcase_04 | AC | 1,024 ms
155,068 KB |
| testcase_05 | AC | 1,011 ms
153,932 KB |
| testcase_06 | AC | 848 ms
109,768 KB |
| testcase_07 | AC | 795 ms
110,096 KB |
| testcase_08 | AC | 817 ms
109,592 KB |
| testcase_09 | AC | 815 ms
109,568 KB |
| testcase_10 | AC | 849 ms
110,316 KB |
| testcase_11 | AC | 826 ms
109,436 KB |
| testcase_12 | AC | 800 ms
110,988 KB |
| testcase_13 | AC | 828 ms
109,468 KB |
| testcase_14 | AC | 808 ms
109,560 KB |
| testcase_15 | AC | 821 ms
110,876 KB |
| testcase_16 | AC | 677 ms
111,084 KB |
| testcase_17 | AC | 882 ms
144,116 KB |
| testcase_18 | AC | 944 ms
152,324 KB |
| testcase_19 | AC | 741 ms
131,200 KB |
| testcase_20 | AC | 808 ms
114,076 KB |
| testcase_21 | AC | 461 ms
96,212 KB |
| testcase_22 | AC | 508 ms
102,732 KB |
| testcase_23 | AC | 966 ms
155,144 KB |
| testcase_24 | AC | 800 ms
118,672 KB |
| testcase_25 | AC | 934 ms
119,628 KB |
| testcase_26 | AC | 1,036 ms
114,408 KB |
| testcase_27 | AC | 698 ms
127,316 KB |
| testcase_28 | AC | 881 ms
146,588 KB |
| testcase_29 | AC | 1,016 ms
116,560 KB |
| testcase_30 | AC | 979 ms
118,748 KB |
| testcase_31 | AC | 783 ms
137,052 KB |
| testcase_32 | AC | 988 ms
117,764 KB |
| testcase_33 | AC | 41 ms
55,596 KB |
| testcase_34 | AC | 41 ms
55,596 KB |
| testcase_35 | AC | 37 ms
55,596 KB |
ソースコード
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]: ノードvの属するheavy-pathのtopと、そこまでの最短パス(通る辺の数)
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-edgeを通り、新しいheavy-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)