### [A.Party](https://codeforces.com/gym/519057/problem/A)↵
↵
<spoiler summary="Hint">↵
Try to think in a level order manner↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
We can notice that the Level of the Employee matters for it to have dinner with the others. Which is basically his level in the graph which decides this. So what we can do is to construct the graph with keeping track of the indegree of the node and doing **BFS** starting from the nodes which have 0 indegree because they are the top level managers and collecting all of them who have the same level to one place.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
import heapq, math↵
from itertools import *↵
from bisect import *↵
from collections import *↵
from sys import stdin, stdout↵
↵
def pr(out):↵
return stdout.write(f"{out}\n")↵
↵
↵
def input():↵
return stdin.readline().rstrip()↵
↵
↵
def int_inp():↵
return int(input())↵
↵
↵
def inp_int_l():↵
return list(map(int, stdin.readline().split()))↵
↵
↵
def inp_l():↵
return stdin.readline().split()↵
↵
def solve():↵
n = int(input())↵
graph = [[] for _ in range(n)]↵
indegree = [0] * n↵
for node in range(n):↵
p = int_inp()↵
if p != -1:↵
graph[p - 1].append(node)↵
indegree[node] += 1↵
level = [[node for node in range(n) if indegree[node] == 0]]↵
queue = deque(level[0])↵
while queue:↵
↵
lev = []↵
for _ in range(len(queue)):↵
node = queue.popleft()↵
for nei in graph[node]:↵
lev.append(nei)↵
queue.append(nei)↵
level.append(lev)↵
count = 0↵
for l in level:↵
if l:↵
count += 1↵
↵
print(count)↵
↵
↵
if __name__ == "__main__":↵
t = 1↵
for _ in range(t):↵
solve()↵
~~~~~↵
</spoiler>↵
↵
### [B. Koxia and Whiteboards](https://codeforces.com/gym/519057/problem/B)↵
↵
<spoiler summary="Hint 1">↵
↵
Notice that the second array is already sorted↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Could you be **Greedy**↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
For maximizing our sum we need to replace the minimum numbers that we have with the minimum number in the second array since the order doesn't matter we can do that pretty easily. We can use heap for getting the minimum number in the first array and since the second array is already sorted we can reverse the second array ans start from the end of the second array and replace the minimum number in the first array by the number at the end. Repeat this process till the second array become empty and return the sum of the numbers that you have left in the first array.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
import heapq↵
↵
t = int(input())↵
for _ in range(t):↵
n, m = map(int, input().split())↵
first_array = list(map(int, input().split()))↵
second_array = list(map(int, input().split()))↵
second_array.reverse()↵
heapq.heapify(first_array)↵
while second_array:↵
heapq.heapreplace(first_array, second_array.pop())↵
print(sum(first_array))↵
↵
~~~~~↵
</spoiler>↵
↵
### [C. Arrow Path](https://codeforces.com/gym/519057/problem/C)↵
↵
<spoiler summary="Hint 1">↵
Try considering the two cases differently.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Identify the source and destination and find the path in between.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Since the Two cases are different we can just do a basic source and destination bfs with two states and check whether the path could lead to the the (2,n) place if we could reach there we can return True else we return False.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
import heapq, math↵
from itertools import *↵
from bisect import *↵
from collections import *↵
from sys import stdin, stdout↵
↵
↵
###########-> Templates <- ##########↵
def pr(out):↵
return stdout.write(f"{out}\n")↵
↵
↵
def input():↵
return stdin.readline().rstrip()↵
↵
↵
def int_inp():↵
return int(input())↵
↵
↵
def inp_int_l():↵
return list(map(int, stdin.readline().split()))↵
↵
↵
def inp_l():↵
return stdin.readline().split()↵
↵
↵
####################################↵
↵
↵
def solve():↵
n = int_inp()↵
grid = [input() for _ in range(2)]↵
↵
def inbound(row, col):↵
return 0 <= row < 2 and 0 <= col < n↵
↵
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]↵
flag = True↵
queue = deque([(0, 0)])↵
visited = set([(0, 0)])↵
↵
while queue:↵
if flag:↵
for _ in range(len(queue)):↵
row, col = queue.popleft()↵
for dr, dc in directions:↵
new_row, new_col = row + dr, col + dc↵
if inbound(new_row, new_col) and (new_row, new_col) not in visited:↵
queue.append((new_row, new_col))↵
visited.add((new_row, new_col))↵
if (row, col) == (1, n - 1):↵
print("YES")↵
return↵
flag = False↵
↵
else:↵
for _ in range(len(queue)):↵
row, col = queue.popleft()↵
if grid[row][col] == ">":↵
new_col = col + 1↵
if inbound(row, new_col) and (row, new_col) not in visited:↵
queue.append((row, new_col))↵
visited.add((row, new_col))↵
↵
elif grid[row][col] == "<":↵
new_col = col - 1↵
if inbound(row, new_col) and (row, new_col) not in visited:↵
queue.append((row, new_col))↵
visited.add((row, new_col))↵
if (row, col) == (1, n - 1):↵
print("YES")↵
return↵
flag = True↵
print("NO")↵
↵
↵
if __name__ == "__main__":↵
t = int(input())E. The Two Routes↵
for _ in range(t):↵
solve()↵
~~~~~↵
</spoiler>↵
↵
### [D. Potions (Hard Version)](https://codeforces.com/gym/519057/problem/D)↵
↵
<spoiler summary="Hint">↵
Could we be Greedy↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Since we are required to drink the most possible number of potions we should drink all of the positive potions. For negative ones we can choose either to use the health that we have already collected on them already or jump them. Since jump and checking whether we should have taken it will take much time. What we can do is to drink the negative potion if we have health greater than it if we don't have we can store the potions that we have drunk till now in a heap and pop from the heap till the health becomes greater than or equal to the negative potion if we couldn't reach that number we just jump it and do the process and we take the maximum length of the heap each time and that will be our answer.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
import heapq, math↵
from itertools import *↵
from bisect import *↵
from collections import *↵
from sys import stdin, stdout↵
↵
↵
###########-> Templates <- ##########↵
def pr(out):↵
return stdout.write(f"{out}\n")↵
↵
↵
def input():↵
return stdin.readline().rstrip()↵
↵
↵
def int_inp():↵
return int(input())↵
↵
↵
def inp_int_l():↵
return list(map(int, stdin.readline().split()))↵
↵
↵
def inp_l():↵
return stdin.readline().split()↵
↵
↵
####################################↵
↵
↵
def solve():↵
n = int_inp()↵
potions = inp_int_l()↵
↵
count = 0↵
max_heap = []↵
curr_health = 0↵
for i in range(n):↵
curr_health += potions[i]↵
heapq.heappush(max_heap, potions[i])↵
while curr_health < 0 and max_heap:↵
curr_health -= heapq.heappop(max_heap)↵
print(len(max_heap))↵
↵
↵
if __name__ == "__main__":↵
t = 1↵
for _ in range(t):↵
solve()↵
~~~~~↵
</spoiler>↵
↵
### [E. The Two Routes](https://codeforces.com/gym/519057/problem/E)↵
↵
<spoiler summary="Hint">↵
Try to construct different roads for the car and the train↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Since we are required to find the minimal time it will be the max time from that of the train and the bus to reach the nth town. For doing that we need to construct the graphs for both the bus and the train but constructing for the bus will consume much time so we can use the train graph and use that graph's complement for getting the graph for the bus. After that the solution is easy we just do source and destination bfs if both the train and the bus could reach the nth city we return the maximum time from the two otherwise if one of them could not reach we return -1.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
import heapq, math↵
from itertools import *↵
from bisect import *↵
from collections import *↵
from sys import stdin, stdout↵
↵
↵
###########-> Templates <- ##########↵
def pr(out):↵
return stdout.write(f"{out}\n")↵
↵
↵
def input():↵
return stdin.readline().rstrip()↵
↵
↵
def int_inp():↵
return int(input())↵
↵
↵
def inp_int_l():↵
return list(map(int, stdin.readline().split()))↵
↵
↵
def inp_l():↵
return stdin.readline().split()↵
↵
↵
####################################↵
↵
↵
def solve():↵
n, m = inp_int_l()↵
graph = [set() for _ in range(n)]↵
for _ in range(m):↵
u, v = inp_int_l()↵
graph[u - 1].add(v - 1)↵
graph[v - 1].add(u - 1)↵
visited = set()↵
↵
train_time = -1↵
queue = deque([(0, 0)]) # Node and time↵
visited.clear()↵
visited.add(0)↵
while queue:↵
node, time = queue.popleft()↵
if node == n - 1:↵
train_time = time↵
break↵
for nei in graph[node]:↵
if nei not in visited:↵
queue.append((nei, time + 1))↵
visited.add(nei)↵
nodes = set(i for i in range(n))↵
bus_time = -1↵
queue = deque([(0, 0)])↵
visited.clear()↵
visited.add(0)↵
while queue:↵
node, time = queue.popleft()↵
nodes.remove(node)↵
if node == n - 1:↵
bus_time = time↵
break↵
neighbors = nodes - graph[node]↵
for nei in neighbors:↵
if nei not in visited:↵
queue.append((nei, time + 1))↵
visited.add(nei)↵
if train_time == -1 or bus_time == -1:↵
print(-1)↵
else:↵
print(max(train_time, bus_time))↵
↵
↵
if __name__ == "__main__":↵
t = 1↵
for _ in range(t):↵
solve()↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="Hint">↵
Try to think in a level order manner↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
We can notice that the Level of the Employee matters for it to have dinner with the others. Which is basically his level in the graph which decides this. So what we can do is to construct the graph with keeping track of the indegree of the node and doing **BFS** starting from the nodes which have 0 indegree because they are the top level managers and collecting all of them who have the same level to one place.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
import heapq, math↵
from itertools import *↵
from bisect import *↵
from collections import *↵
from sys import stdin, stdout↵
↵
def pr(out):↵
return stdout.write(f"{out}\n")↵
↵
↵
def input():↵
return stdin.readline().rstrip()↵
↵
↵
def int_inp():↵
return int(input())↵
↵
↵
def inp_int_l():↵
return list(map(int, stdin.readline().split()))↵
↵
↵
def inp_l():↵
return stdin.readline().split()↵
↵
def solve():↵
n = int(input())↵
graph = [[] for _ in range(n)]↵
indegree = [0] * n↵
for node in range(n):↵
p = int_inp()↵
if p != -1:↵
graph[p - 1].append(node)↵
indegree[node] += 1↵
level = [[node for node in range(n) if indegree[node] == 0]]↵
queue = deque(level[0])↵
while queue:↵
↵
lev = []↵
for _ in range(len(queue)):↵
node = queue.popleft()↵
for nei in graph[node]:↵
lev.append(nei)↵
queue.append(nei)↵
level.append(lev)↵
count = 0↵
for l in level:↵
if l:↵
count += 1↵
↵
print(count)↵
↵
↵
if __name__ == "__main__":↵
t = 1↵
for _ in range(t):↵
solve()↵
~~~~~↵
</spoiler>↵
↵
### [B. Koxia and Whiteboards](https://codeforces.com/gym/519057/problem/B)↵
↵
<spoiler summary="Hint 1">↵
↵
Notice that the second array is already sorted↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Could you be **Greedy**↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
For maximizing our sum we need to replace the minimum numbers that we have with the minimum number in the second array since the order doesn't matter we can do that pretty easily. We can use heap for getting the minimum number in the first array and since the second array is already sorted we can reverse the second array ans start from the end of the second array and replace the minimum number in the first array by the number at the end. Repeat this process till the second array become empty and return the sum of the numbers that you have left in the first array.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
import heapq↵
↵
t = int(input())↵
for _ in range(t):↵
n, m = map(int, input().split())↵
first_array = list(map(int, input().split()))↵
second_array = list(map(int, input().split()))↵
second_array.reverse()↵
heapq.heapify(first_array)↵
while second_array:↵
heapq.heapreplace(first_array, second_array.pop())↵
print(sum(first_array))↵
↵
~~~~~↵
</spoiler>↵
↵
### [C. Arrow Path](https://codeforces.com/gym/519057/problem/C)↵
↵
<spoiler summary="Hint 1">↵
Try considering the two cases differently.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Identify the source and destination and find the path in between.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Since the Two cases are different we can just do a basic source and destination bfs with two states and check whether the path could lead to the the (2,n) place if we could reach there we can return True else we return False.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
import heapq, math↵
from itertools import *↵
from bisect import *↵
from collections import *↵
from sys import stdin, stdout↵
↵
↵
###########-> Templates <- ##########↵
def pr(out):↵
return stdout.write(f"{out}\n")↵
↵
↵
def input():↵
return stdin.readline().rstrip()↵
↵
↵
def int_inp():↵
return int(input())↵
↵
↵
def inp_int_l():↵
return list(map(int, stdin.readline().split()))↵
↵
↵
def inp_l():↵
return stdin.readline().split()↵
↵
↵
####################################↵
↵
↵
def solve():↵
n = int_inp()↵
grid = [input() for _ in range(2)]↵
↵
def inbound(row, col):↵
return 0 <= row < 2 and 0 <= col < n↵
↵
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]↵
flag = True↵
queue = deque([(0, 0)])↵
visited = set([(0, 0)])↵
↵
while queue:↵
if flag:↵
for _ in range(len(queue)):↵
row, col = queue.popleft()↵
for dr, dc in directions:↵
new_row, new_col = row + dr, col + dc↵
if inbound(new_row, new_col) and (new_row, new_col) not in visited:↵
queue.append((new_row, new_col))↵
visited.add((new_row, new_col))↵
if (row, col) == (1, n - 1):↵
print("YES")↵
return↵
flag = False↵
↵
else:↵
for _ in range(len(queue)):↵
row, col = queue.popleft()↵
if grid[row][col] == ">":↵
new_col = col + 1↵
if inbound(row, new_col) and (row, new_col) not in visited:↵
queue.append((row, new_col))↵
visited.add((row, new_col))↵
↵
elif grid[row][col] == "<":↵
new_col = col - 1↵
if inbound(row, new_col) and (row, new_col) not in visited:↵
queue.append((row, new_col))↵
visited.add((row, new_col))↵
if (row, col) == (1, n - 1):↵
print("YES")↵
return↵
flag = True↵
print("NO")↵
↵
↵
if __name__ == "__main__":↵
t = int(input())E. The Two Routes↵
for _ in range(t):↵
solve()↵
~~~~~↵
</spoiler>↵
↵
### [D. Potions (Hard Version)](https://codeforces.com/gym/519057/problem/D)↵
↵
<spoiler summary="Hint">↵
Could we be Greedy↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Since we are required to drink the most possible number of potions we should drink all of the positive potions. For negative ones we can choose either to use the health that we have already collected on them already or jump them. Since jump and checking whether we should have taken it will take much time. What we can do is to drink the negative potion if we have health greater than it if we don't have we can store the potions that we have drunk till now in a heap and pop from the heap till the health becomes greater than or equal to the negative potion if we couldn't reach that number we just jump it and do the process and we take the maximum length of the heap each time and that will be our answer.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
import heapq, math↵
from itertools import *↵
from bisect import *↵
from collections import *↵
from sys import stdin, stdout↵
↵
↵
###########-> Templates <- ##########↵
def pr(out):↵
return stdout.write(f"{out}\n")↵
↵
↵
def input():↵
return stdin.readline().rstrip()↵
↵
↵
def int_inp():↵
return int(input())↵
↵
↵
def inp_int_l():↵
return list(map(int, stdin.readline().split()))↵
↵
↵
def inp_l():↵
return stdin.readline().split()↵
↵
↵
####################################↵
↵
↵
def solve():↵
n = int_inp()↵
potions = inp_int_l()↵
↵
count = 0↵
max_heap = []↵
curr_health = 0↵
for i in range(n):↵
curr_health += potions[i]↵
heapq.heappush(max_heap, potions[i])↵
while curr_health < 0 and max_heap:↵
curr_health -= heapq.heappop(max_heap)↵
print(len(max_heap))↵
↵
↵
if __name__ == "__main__":↵
t = 1↵
for _ in range(t):↵
solve()↵
~~~~~↵
</spoiler>↵
↵
### [E. The Two Routes](https://codeforces.com/gym/519057/problem/E)↵
↵
<spoiler summary="Hint">↵
Try to construct different roads for the car and the train↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Since we are required to find the minimal time it will be the max time from that of the train and the bus to reach the nth town. For doing that we need to construct the graphs for both the bus and the train but constructing for the bus will consume much time so we can use the train graph and use that graph's complement for getting the graph for the bus. After that the solution is easy we just do source and destination bfs if both the train and the bus could reach the nth city we return the maximum time from the two otherwise if one of them could not reach we return -1.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
import heapq, math↵
from itertools import *↵
from bisect import *↵
from collections import *↵
from sys import stdin, stdout↵
↵
↵
###########-> Templates <- ##########↵
def pr(out):↵
return stdout.write(f"{out}\n")↵
↵
↵
def input():↵
return stdin.readline().rstrip()↵
↵
↵
def int_inp():↵
return int(input())↵
↵
↵
def inp_int_l():↵
return list(map(int, stdin.readline().split()))↵
↵
↵
def inp_l():↵
return stdin.readline().split()↵
↵
↵
####################################↵
↵
↵
def solve():↵
n, m = inp_int_l()↵
graph = [set() for _ in range(n)]↵
for _ in range(m):↵
u, v = inp_int_l()↵
graph[u - 1].add(v - 1)↵
graph[v - 1].add(u - 1)↵
visited = set()↵
↵
train_time = -1↵
queue = deque([(0, 0)]) # Node and time↵
visited.clear()↵
visited.add(0)↵
while queue:↵
node, time = queue.popleft()↵
if node == n - 1:↵
train_time = time↵
break↵
for nei in graph[node]:↵
if nei not in visited:↵
queue.append((nei, time + 1))↵
visited.add(nei)↵
nodes = set(i for i in range(n))↵
bus_time = -1↵
queue = deque([(0, 0)])↵
visited.clear()↵
visited.add(0)↵
while queue:↵
node, time = queue.popleft()↵
nodes.remove(node)↵
if node == n - 1:↵
bus_time = time↵
break↵
neighbors = nodes - graph[node]↵
for nei in neighbors:↵
if nei not in visited:↵
queue.append((nei, time + 1))↵
visited.add(nei)↵
if train_time == -1 or bus_time == -1:↵
print(-1)↵
else:↵
print(max(train_time, bus_time))↵
↵
↵
if __name__ == "__main__":↵
t = 1↵
for _ in range(t):↵
solve()↵
~~~~~↵
</spoiler>↵
↵
