Problem:


Score : 1000 points

Problem Statement

There is a simple undirected graph with N vertices and M edges.
The vertices are numbered 1 through N, and the edges are numbered 1 through M.
Edge i connects Vertex U_i and V_i.
Also, Vertex i has two predetermined integers A_i and B_i.
You will play the following game on this graph.

First, choose one vertex and stand on it, with W yen (the currency of Japan) in your pocket.
Here, A_s \leq W must hold, where s is the vertex you choose.
Then, perform the following two kinds of operations any number of times in any order:

Choose one vertex v that is directly connected by an edge to the vertex you are standing on, and move to vertex v. Here, you need to have at least A_v yen in your pocket when you perform this move.

Donate B_v yen to the vertex v you are standing on. Here, the amount of money in your pocket must not become less than 0 yen.

You win the game when you donate once to every vertex.
Find the smallest initial amount of money W that enables you to win the game.

Constraints

1 \leq N \leq 10^5

N-1 \leq M \leq 10^5

1 \leq A_i,B_i \leq 10^9

1 \leq U_i < V_i \leq N

The given graph is connected and simple (there is at most one edge between any pair of vertices).

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
:
A_N B_N
U_1 V_1
U_2 V_2
:
U_M V_M

Output

Print the smallest initial amount of money W that enables you to win the game.

Sample Input 1

4 5
3 1
1 2
4 1
6 2
1 2
2 3
2 4
1 4
3 4

Sample Output 1

6

If you have 6 yen initially, you can win the game as follows:

Stand on Vertex 4. This is possible since you have not less than 6 yen.

Donate 2 yen to Vertex 4. Now you have 4 yen.

Move to Vertex 3. This is possible since you have not less than 4 yen.

Donate 1 yen to Vertex 3. Now you have 3 yen.

Move to Vertex 2. This is possible since you have not less than 1 yen.

Move to Vertex 1. This is possible since you have not less than 3 yen.

Donate 1 yen to Vertex 1. Now you have 2 yen.

Move to Vertex 2. This is possible since you have not less than 1 yen.

Donate 2 yen to Vertex 2. Now you have 0 yen.

If you have less than 6 yen initially, you cannot win the game. Thus, the answer is 6.

Sample Input 2

5 8
6 4
15 13
15 19
15 1
20 7
1 3
1 4
1 5
2 3
2 4
2 5
3 5
4 5

Sample Output 2

44

Sample Input 3

9 10
131 2
98 79
242 32
231 38
382 82
224 22
140 88
209 70
164 64
6 8
1 6
1 4
1 3
4 7
4 9
3 7
3 9
5 9
2 5

Sample Output 3

582



Sample input:
4 5
3 1
1 2
4 1
6 2
1 2
2 3
2 4
1 4
3 4


Sample output:
6

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        """
        return self._sizes[self.root(x)]


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


N, M = list(map(int, sys.stdin.buffer.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(N)]))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

# from libs.debug import plot_graph
#
# plot_graph(VU)

graph = [[] for _ in range(N)]
for v, u in VU:
    v -= 1
    u -= 1
    graph[v].append(u)
    graph[u].append(v)

reqs = [max(a, b) for a, b in zip(A, B)]
uses = list(B)

idx = argsort(A)
uf = UnionFind(size=N)
seen = [False] * N
ans = [INF] * N
for v in idx:
    seen[v] = True
    roots = set()
    for u in graph[v]:
        if not seen[u]:
            continue
        roots.add(uf.root(u))

    use_all = uses[v]
    for r in roots:
        use_all += uses[r]

    # v が最後
    req_v = reqs[v] + use_all - uses[v]
    for r in roots:
        req_v = min(req_v, max(reqs[r], reqs[v] - uses[v]) + use_all - uses[r])

    for r in roots:
        uf.unite(v, r)
    reqs[uf.root(v)] = req_v
    uses[uf.root(v)] = use_all
ans = reqs[uf.root(0)]
print(ans)

Submission status: Accepted

Solution code:
class dsu:
    def __init__(self, n=0):
        self._n = n
        self.parent_or_size = [-1] * n
    
    def merge(self, a: int, b: int) -> int:
        x = self.leader(a)
        y = self.leader(b)
        if x == y:
            return x
        if self.parent_or_size[x] > self.parent_or_size[y]:
            x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x
    
    def same(self, a: int, b: int) -> bool:
        return self.leader(a) == self.leader(b)
    
    def leader(self, a: int) -> int:
        x = a
        while self.parent_or_size[x] >= 0:
            x = self.parent_or_size[x]
        while a != x:
            self.parent_or_size[a], a = x, self.parent_or_size[a]
        return x
    
    def size(self, a: int) -> int:
        return -self.parent_or_size[self.leader(a)]
    
    def groups(self):
        g = [[] for _ in range(self._n)]
        for i in range(self._n):
            g[self.leader(i)].append(i)
        return list(c for c in g if c)

n, m = map(int, input().split())
vdata = [] # (required, gain)
for _ in range(n):
    a, b = map(int, input().split())
    vdata.append((max(a - b, 0), b))
to = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1; v -= 1
    to[u].append(v)
    to[v].append(u)
s = dsu(n)
dp = vdata.copy() # (extra, tot_gain)
visited = [False] * n
for u in sorted(range(n), key=lambda i: vdata[i][0]):
    req, gain = vdata[u]
    frm = {u}
    for v in to[u]:
        if visited[v]:
            frm.add(s.leader(v))
    mnextra = 10 ** 18
    for v in frm:
        e, g = dp[v]
        e += max(req - (e + g), 0)
        if e < mnextra:
            mnextra, mni = e, v
    extra, tot_gain = mnextra, sum(dp[v][1] for v in frm)
    for v in frm:
        s.merge(u, v)
    dp[s.leader(u)] = extra, tot_gain
    visited[u] = True
ans = sum(dp[s.leader(0)])
print(ans)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        """
        return self._sizes[self.root(x)]


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


N, M = list(map(int, sys.stdin.buffer.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(N)]))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

# from libs.debug import plot_graph
#
# plot_graph(VU)

graph = [[] for _ in range(N)]
for v, u in VU:
    v -= 1
    u -= 1
    graph[v].append(u)
    graph[u].append(v)

reqs = [max(a, b) for a, b in zip(A, B)]
uses = list(B)

idx = argsort([a - b for a, b in zip(A, B)])
uf = UnionFind(size=N)
seen = [False] * N
ans = [INF] * N
for v in idx:
    seen[v] = True
    roots = set()
    for u in graph[v]:
        if not seen[u]:
            continue
        roots.add(uf.root(u))

    use_all = uses[v]
    for r in roots:
        use_all += uses[r]

    # v が最後
    req_v = reqs[v] + use_all - uses[v]
    for r in roots:
        req_v = min(req_v, max(reqs[r], reqs[v] - uses[v]) + use_all - uses[r])

    for r in roots:
        uf.unite(v, r)
    reqs[uf.root(v)] = req_v
    uses[uf.root(v)] = use_all
ans = reqs[uf.root(0)]
print(ans)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        """
        return self._sizes[self.root(x)]


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


N, M = list(map(int, sys.stdin.buffer.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(N)]))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

# from libs.debug import plot_graph
#
# plot_graph(VU)

graph = [[] for _ in range(N)]
for v, u in VU:
    v -= 1
    u -= 1
    graph[v].append(u)
    graph[u].append(v)

# 解説
# C[v] = A[v] - B[v]
# C の小さい順にグラフを構築して、部分グラフごとに答えを持つ
reqs = [max(0, a - b) for a, b in zip(A, B)]
uses = list(B)

idx = argsort(reqs)
uf = UnionFind(size=N)
seen = [False] * N
ans = [INF] * N
for v in idx:
    # v: 今までに見た中で C が最大の頂点
    seen[v] = True
    roots = set()
    for u in graph[v]:
        if not seen[u]:
            continue
        roots.add(uf.root(u))

    use_all = uses[v]
    for r in roots:
        use_all += uses[r]
    # v を最初にする場合
    req_v = reqs[v] + use_all
    for r in roots:
        # r のどれかを root とする部分グラフを最初にする場合
        # C[v] が今まで見たうち最大なので v に来たあとは好きな頂点まで行ける
        req_v = min(req_v, max(reqs[r], reqs[v]) + use_all - uses[r])

    for r in roots:
        uf.unite(v, r)
    reqs[uf.root(v)] = req_v
    uses[uf.root(v)] = use_all
ans = reqs[uf.root(0)]
print(ans)

Submission status: Runtime Error

Solution code:
import sys,random,time,bisect
input=sys.stdin.buffer.readline

start=time.time()
N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[] for i in range(2**9)]
def make_dp(v):
    t=[[0,0] for i in range(15)]
    V=v
    id=0
    while v>=1:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    temp=[[0,0] for i in range(2**n)]
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]
    temp.sort(key=lambda x:x[1])
    for i in range(1,2**n):
        temp[i][0]=max(temp[i][0],temp[i-1][0])

    dp[V]=[0]*(10**5+1)
    for i in range(2**n-1):
        L=temp[i][1]
        R=temp[i+1][1]
        if L>10**5:
            break
        elif R>10**5:
            R=10**5+1
        for j in range(L,R):
            dp[V][j]=temp[i][0]
    else:
        L=temp[-1][1]
        if L<=10**5:
            for j in range(L,10**5+1):
                dp[V][j]=temp[-1][0]

MAX=min(2**9,N+1)
for i in range(1,MAX):
    make_dp(i)

Q=int(input())
query=[[] for i in range(N+1)]
for i in range(Q):
    v,L=map(int,input().split())
    query[v].append((L,i))

ans=[0]*Q
temp=[[0,0] for i in range(2**9)]
solved=[False]*(N+1)

def solve(v):
    subq=[]
    t=[]
    check=[]
    id=0
    while v>=2**9:
        t.append(vw[v])
        subq.append(v)
        check.append(id)
        id+=1
        v//=2
    if not subq:
        subq=[v]
        check=[0]

    t=t[::-1]
    n=len(t)
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]

    for i in range(len(check)):
        V=subq[i]
        if not solved[V]:
            solved[V]=True
            for L,ID in query[V]:
                res=0
                m=n-check[i]
                for i in range(2**m):
                    if L>=temp[i][1]:
                        res=max(res,temp[i][0]+dp[v][L-temp[i][1]])
                ans[ID]=res

for i in range(1,N+1):
    if query[i] and not solved[i]:
        solve(i)

for i in range(Q):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        """
        return self._sizes[self.root(x)]


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


N, M = list(map(int, sys.stdin.buffer.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(N)]))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

# from libs.debug import plot_graph
#
# plot_graph(VU)

graph = [[] for _ in range(M)]
for v, u in VU:
    v -= 1
    u -= 1
    graph[v].append(u)
    graph[u].append(v)

# 解説
# C[v] = A[v] - B[v]
# C の小さい順にグラフを構築して、部分グラフごとに答えを持つ
reqs = [max(0, a - b) for a, b in zip(A, B)]
uses = list(B)

idx = argsort(reqs)
uf = UnionFind(size=N)
seen = [False] * N
ans = [INF] * N
for v in idx:
    # v: 今までに見た中で C が最大の頂点
    seen[v] = True
    roots = set()
    for u in graph[v]:
        if not seen[u]:
            continue
        roots.add(uf.root(u))

    use_all = uses[v]
    for r in roots:
        use_all += uses[r]
    # v を最初にする場合
    req_v = reqs[v] + use_all
    for r in roots:
        # r のどれかを root とする部分グラフを最初にする場合
        # C[v] が今まで見たうち最大なので v に来たあとは好きな頂点まで行ける
        req_v = min(req_v, max(reqs[r], reqs[v]) + use_all - uses[r])

    for r in roots:
        uf.unite(v, r)
    reqs[uf.root(v)] = req_v
    uses[uf.root(v)] = use_all
ans = reqs[uf.root(0)]
print(ans)

Submission status: Runtime Error

Solution code:
import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

n = int(input())

a = l()

ans = 0
l = 0
r = 0
su = 0
for i in range(N):
	while(r < N and (su^a[r]) == (su + a[r])):
		su += a[r]
		r += 1
	ans += r -i
	if r == i:
		r += 1
	else:
		su -= a[l]
print(ans)

Submission status: Runtime Error

Solution code:
N, K, Q = [int(i) for i in input().split(" ")]
A = [int(a) for a in input().split(" ")]

_min = min(A)
A.sort()
for k in range(K):
    _max = A.pop(0)
print(_max - _min)