Try to think in a level order manner

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.

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()

Notice that the second array is already sorted

Could you be Greedy

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.

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))

Try considering the two cases differently.

Identify the source and destination and find the path in between.

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.

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()

Could we be Greedy

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.

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()

Try to construct different roads for the car and the train

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.

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()