🔖

# AtCoder ABC187 個人的メモ

2021/01/03に公開

abcd4完

## A - Large Digits

A, B = input().split()

a = 0
b = 0
for i in A:
a += int(i)
for i in B:
b += int(i)

if a >= b:
print(a)
else:
print(b)



## B - Gentle Pairs

https://atcoder.jp/contests/abc187/editorial/484

from itertools import combinations

N = int(input())
pnts = [list(map(int, input().split())) for _ in range(N)]

ans = 0
for a, b in combinations(pnts, 2):
res = (b[1] - a[1]) / (b[0] - a[0])
if -1 <= res <= 1:
ans += 1

print(ans)



## C - 1-SAT

N = int(input())

zero_set = set()
one_set = set()
for _ in range(N):
s = input()
if s[0] == "!":
else:

ans = "satisfiable"
for i in zero_set:
if i in one_set:
ans = i

print(ans)



## D - Choose Me

https://atcoder.jp/contests/abc187/editorial/486

N = int(input())
score = 0
speach = []
for _ in range(N):
a, b = map(int, input().split())
score -= a
speach.append((a * 2 + b))

ans = 0
speach.sort(reverse=True)
for i in speach:
score += i
ans += 1
if score > 0:
break

print(ans)



## E - Through Path

tと頂点a,bのどちらが親かで以下の様に場合分けできる

• t=1かつaが親
aaの先祖全てにxを足す
又は，bbの子孫全てに-xを足し，木全体(根と根の子孫)にxを足す

• t=1かつbが親
aaの子孫全てにxを足す

• t=2かつaが親
bbの子孫全てにxを足す

• t=2かつbが親
bbの先祖全てにxを足す
又は，aaの子孫全てに-xを足し，木全体(根と根の子孫)にxを足す

これらの操作は各頂点にのみxを足しておけば，根から累積和をとっていくことで後からまとめて計算できる
これで，各クエリでの操作はO(1)で済む

1. 木を作る
2. 2頂点間の高さを比較するために，木の各頂点の高さを調べる
3. クエリ処理
4. 累積和
from collections import deque

N = int(input())
edge = []
graph = [[] for _ in range(N)]
for _ in range(N - 1):
a, b = map(lambda x: int(x) - 1, input().split())
edge.append((a, b))
graph[a].append(b)
graph[b].append(a)

# 2頂点a,bのどちらが親かを判定するために各頂点の高さを調べておく
queue = deque([0])
depth = [-1] * N
depth[0] = 0
while queue:
now = queue.popleft()
for i in graph[now]:
if depth[i] != -1:
continue
depth[i] = depth[now] + 1
queue.append(i)

node_num = [0] * N
Q = int(input())
for _ in range(Q):
t, e, x = map(int, input().split())
a, b = edge[e - 1]
if t == 1:
if depth[a] < depth[b]:
node_num[b] -= x
node_num[0] += x
else:
node_num[a] += x
else:
if depth[a] < depth[b]:
node_num[b] += x
else:
node_num[a] -= x
node_num[0] += x

queue = deque([0])
while queue:
now = queue.popleft()
for i in graph[now]:
if depth[i] < depth[now]:
continue
node_num[i] += node_num[now]
queue.append(i)

print(*node_num, sep="\n")



ログインするとコメントできます