結果

問題 No.2642 Don't cut line!
ユーザー 👑 timitimi
提出日時 2024-02-23 16:03:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,103 ms / 4,000 ms
コード長 3,550 bytes
コンパイル時間 1,155 ms
コンパイル使用メモリ 81,572 KB
実行使用メモリ 157,472 KB
最終ジャッジ日時 2024-02-23 16:04:20
合計ジャッジ時間 28,949 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
55,616 KB
testcase_01 AC 1,034 ms
157,472 KB
testcase_02 AC 1,042 ms
157,336 KB
testcase_03 AC 1,103 ms
157,336 KB
testcase_04 AC 1,044 ms
157,208 KB
testcase_05 AC 1,067 ms
157,472 KB
testcase_06 AC 616 ms
109,548 KB
testcase_07 AC 649 ms
110,188 KB
testcase_08 AC 628 ms
110,556 KB
testcase_09 AC 635 ms
110,184 KB
testcase_10 AC 651 ms
110,824 KB
testcase_11 AC 632 ms
110,468 KB
testcase_12 AC 660 ms
111,344 KB
testcase_13 AC 618 ms
110,584 KB
testcase_14 AC 658 ms
110,316 KB
testcase_15 AC 639 ms
111,344 KB
testcase_16 AC 881 ms
156,340 KB
testcase_17 AC 947 ms
146,768 KB
testcase_18 AC 981 ms
152,088 KB
testcase_19 AC 781 ms
133,128 KB
testcase_20 AC 838 ms
114,836 KB
testcase_21 AC 572 ms
103,616 KB
testcase_22 AC 679 ms
136,444 KB
testcase_23 AC 1,038 ms
155,860 KB
testcase_24 AC 712 ms
117,152 KB
testcase_25 AC 767 ms
115,788 KB
testcase_26 AC 825 ms
114,276 KB
testcase_27 AC 697 ms
128,280 KB
testcase_28 AC 936 ms
149,896 KB
testcase_29 AC 842 ms
113,984 KB
testcase_30 AC 770 ms
115,576 KB
testcase_31 AC 836 ms
138,624 KB
testcase_32 AC 773 ms
114,272 KB
testcase_33 AC 41 ms
55,616 KB
testcase_34 AC 41 ms
55,616 KB
testcase_35 AC 41 ms
55,616 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