#953777 (PyPy3) No.2642 Don't cut line!

提出ソース

結果

問題	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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	AC	1,037 ms 155,804 KB
testcase_02	AC	1,024 ms 154,804 KB
testcase_03	AC	1,010 ms 154,120 KB
testcase_04	AC	1,021 ms 155,396 KB
testcase_05	AC	1,010 ms 154,656 KB
testcase_06	AC	802 ms 110,060 KB
testcase_07	AC	801 ms 110,344 KB
testcase_08	AC	776 ms 110,204 KB
testcase_09	AC	809 ms 109,848 KB
testcase_10	AC	831 ms 110,812 KB
testcase_11	AC	783 ms 109,692 KB
testcase_12	AC	791 ms 111,460 KB
testcase_13	AC	790 ms 110,208 KB
testcase_14	AC	789 ms 109,908 KB
testcase_15	AC	817 ms 111,536 KB
testcase_16	AC	667 ms 111,620 KB
testcase_17	AC	884 ms 144,640 KB
testcase_18	AC	947 ms 152,404 KB
testcase_19	AC	755 ms 131,692 KB
testcase_20	AC	813 ms 114,716 KB
testcase_21	AC	461 ms 96,372 KB
testcase_22	AC	499 ms 103,132 KB
testcase_23	AC	947 ms 155,844 KB
testcase_24	AC	821 ms 118,768 KB
testcase_25	AC	925 ms 120,524 KB
testcase_26	AC	1,010 ms 114,960 KB
testcase_27	AC	674 ms 127,612 KB
testcase_28	AC	907 ms 146,720 KB
testcase_29	AC	1,012 ms 117,232 KB
testcase_30	AC	959 ms 119,136 KB
testcase_31	AC	796 ms 137,336 KB
testcase_32	AC	1,011 ms 119,020 KB
testcase_33	AC	44 ms 56,256 KB
testcase_34	AC	44 ms 56,508 KB
testcase_35	AC	40 ms 54,168 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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)

yukicoder

結果

テストケース

ソースコード