結果

問題 No.2642 Don't cut line!
ユーザー timitimi
提出日時 2024-02-23 16:03:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 837 ms / 4,000 ms
コード長 3,550 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,600 KB
実行使用メモリ 158,428 KB
最終ジャッジ日時 2024-09-29 05:11:08
合計ジャッジ時間 23,357 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
54,556 KB
testcase_01 AC 811 ms
158,128 KB
testcase_02 AC 811 ms
157,872 KB
testcase_03 AC 837 ms
158,428 KB
testcase_04 AC 815 ms
158,008 KB
testcase_05 AC 825 ms
157,884 KB
testcase_06 AC 501 ms
110,716 KB
testcase_07 AC 493 ms
111,080 KB
testcase_08 AC 496 ms
110,832 KB
testcase_09 AC 511 ms
110,844 KB
testcase_10 AC 509 ms
111,232 KB
testcase_11 AC 514 ms
111,104 KB
testcase_12 AC 507 ms
112,128 KB
testcase_13 AC 512 ms
110,972 KB
testcase_14 AC 517 ms
110,840 KB
testcase_15 AC 524 ms
111,992 KB
testcase_16 AC 684 ms
156,108 KB
testcase_17 AC 771 ms
146,740 KB
testcase_18 AC 831 ms
152,784 KB
testcase_19 AC 618 ms
133,740 KB
testcase_20 AC 693 ms
115,456 KB
testcase_21 AC 452 ms
104,412 KB
testcase_22 AC 564 ms
137,064 KB
testcase_23 AC 831 ms
155,836 KB
testcase_24 AC 576 ms
118,364 KB
testcase_25 AC 604 ms
116,788 KB
testcase_26 AC 676 ms
114,284 KB
testcase_27 AC 570 ms
128,348 KB
testcase_28 AC 756 ms
149,908 KB
testcase_29 AC 648 ms
114,648 KB
testcase_30 AC 615 ms
116,132 KB
testcase_31 AC 667 ms
139,672 KB
testcase_32 AC 636 ms
114,944 KB
testcase_33 AC 40 ms
54,992 KB
testcase_34 AC 37 ms
55,572 KB
testcase_35 AC 38 ms
55,448 KB
権限があれば一括ダウンロードができます

ソースコード

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

from collections import deque
class LowestCommonAncestor:
    def __init__(self, n):
        self._n = n
        self._logn = 0
        v = 1
        while v <= self._n:
            v *= 2
            self._logn += 1
        self._depth = [0] * self._n
        self._distance = [0] * self._n
        self._ancestor = [[-1] * self._n for _ in range(self._logn)]
        self.dp = [[-1] * self._n for _ in range(self._logn)]
        self._G = [[] for i in range(self._n)]
        

    def add_edge(self, u, v, w=1):
        self._G[u].append((v, w))
        self._G[v].append((u, w))

    def build(self, root=0):
        stack = [root]
        while stack:
            cur = stack.pop()
            for nex, w in self._G[cur]:
                if self._ancestor[0][nex] != cur and self._ancestor[0][cur] != nex:
                    self._ancestor[0][nex] = cur
                    self._depth[nex] = self._depth[cur] + 1
                    self._distance[nex] = self._distance[cur] + w
                    stack.append(nex)
                    self.dp[0][nex] = w 

        for k in range(1, self._logn):
            for i in range(self._n):
                if self._ancestor[k - 1][i] == -1:
                    self._ancestor[k][i] = -1
                    self.dp[k][i] = self.dp[k-1][i]
                else:
                    self._ancestor[k][i] = self._ancestor[k - 1][self._ancestor[k - 1][i]]
                    self.dp[k][i] = max(self.dp[k-1][i], self.dp[k-1][self._ancestor[k - 1][i]])

    def lca(self, u, v):
        if self._depth[u] > self._depth[v]:
            u, v = v, u
        for k in range(self._logn - 1, -1, -1):
            if ((self._depth[v] - self._depth[u]) >> k) & 1:
                v = self._ancestor[k][v]
        if u == v:
            return u
        for k in range(self._logn - 1, -1, -1):
            if self._ancestor[k][u] != self._ancestor[k][v]:
                u = self._ancestor[k][u]
                v = self._ancestor[k][v]
        return self._ancestor[0][u]

    def distance(self, u, v):
        return self._distance[u] + self._distance[v] - 2 * self._distance[self.lca(u, v)]

    def query(self, a, b):
        lca = self.lca(a, b)
        return max(self.max_edge(a, self._depth[a] - self._depth[lca])
                   , self.max_edge(b, self._depth[b] - self._depth[lca]))
        
    def max_edge(self, a, d):
        now = -10 ** 18
        for i in range(self._logn):
            if (d >> i) & 1:
                now = max(now, self.dp[i][a])
                a = self._ancestor[i][a]
        return now
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=[]
T = LowestCommonAncestor(N)
cost=0;pp=0
for w,u,v,p in A:
  if not same(u,v):
    union(u,v)
    AA.append((u,v,w))
    T.add_edge(u,v,w)
    pp=max(p,pp)
    cost+=w 
  else:
    B.append((p,u,v,w))

if cost>C:
  print(-1)
  exit()
  
ans=pp
T.build(0)
for p,u,v,w in B:
  #print(pp,p)
  #print(cost+w-T.query(u,v))
  if cost+w-T.query(u,v)<=C:
			ans=max(ans,max(p,pp))
        
print(ans)
0