Count Seconds (Codeforces 1704E)
Tags: Math, graphs

Cirno has a DAG (Directed Acyclic Graph) with $$$n$$$ nodes and $$$m$$$ edges. The graph has exactly one node that has no out edges. The $$$i$$$-th node has an integer $$$a_i$$$ on it.Every second the following happens: Let $$$S$$$ be the set of nodes $$$x$$$ that have $$$a_x > 0$$$. For all $$$x \in S$$$, $$$1$$$ is subtracted from $$$a_x$$$, and then for each node $$$y$$$, such that there is an edge from $$$x$$$ to $$$y$$$, $$$1$$$ is added to $$$a_y$$$.Find the first moment of time when all $$$a_i$$$ become $$$0$$$. Since the answer can be very large, output it modulo $$$998\,244\,353$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. Description of test cases follows.The first line of each test case contains two integers $$$n, m$$$ ($$$1 \leq n, m \leq 1000$$$) — the number of vertices and edges in the graph.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — the integer on vertices.Each line of the following $$$m$$$ lines contains two integers $$$x, y$$$ ($$$1 \leq x, y \leq n$$$), represent a directed edge from $$$x$$$ to $$$y$$$. It is guaranteed that the graph is a DAG with no multi-edges, and there is exactly one node that has no out edges.It is guaranteed that both sum of $$$n$$$ and sum of $$$m$$$ over all test cases are less than or equal to $$$10\,000$$$.

Output: For each test case, print an integer in a separate line — the first moment of time when all $$$a_i$$$ become $$$0$$$, modulo $$$998\,244\,353$$$.

Note: In the first test case: At time $$$0$$$, the values of the nodes are $$$[1, 1, 1]$$$.  At time $$$1$$$, the values of the nodes are $$$[0, 1, 1]$$$.  At time $$$2$$$, the values of the nodes are $$$[0, 0, 1]$$$.  At time $$$3$$$, the values of the nodes are $$$[0, 0, 0]$$$.So the answer is $$$3$$$. In the second test case:  At time $$$0$$$, the values of the nodes are $$$[1, 0, 0, 0, 0]$$$.  At time $$$1$$$, the values of the nodes are $$$[0, 1, 0, 0, 1]$$$.  At time $$$2$$$, the values of the nodes are $$$[0, 0, 1, 0, 0]$$$.  At time $$$3$$$, the values of the nodes are $$$[0, 0, 0, 1, 0]$$$.  At time $$$4$$$, the values of the nodes are $$$[0, 0, 0, 0, 1]$$$.  At time $$$5$$$, the values of the nodes are $$$[0, 0, 0, 0, 0]$$$.  So the answer is $$$5$$$.In the third test case:The first moment of time when all $$$a_i$$$ become $$$0$$$ is $$$6\cdot 998244353 + 4$$$.

Sample Inputs:
5
3 2
1 1 1
1 2
2 3
5 5
1 0 0 0 0
1 2
2 3
3 4
4 5
1 5
10 11
998244353 0 0 0 998244353 0 0 0 0 0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 3
7 9
5 6
1293 1145 9961 9961 1919
1 2
2 3
3 4
5 4
1 4
2 4
6 9
10 10 10 10 10 10
1 2
1 3
2 3
4 3
6 3
3 5
6 5
6 1
6 2

Sample Outputs:
3
5
4
28010
110

Solution (Python):
from functools import lru_cache
import sys
import io
import os
MOD = 998244353
sys.setrecursionlimit(5000)

def main():
    for _ in range(read_int()):
        (n, m) = read_int_tuple()
        a = read_int_list()
        rg = [[] for _ in range(n)]
        ss = set(range(n))
        for _ in range(m):
            (u, v) = read_int_tuple()
            rg[v - 1].append(u - 1)
            ss.discard(u - 1)

        @lru_cache(None)
        def dfs(u):
            r = a[u]
            (s, e) = (1, a[u])
            book = []
            for v in rg[u]:
                (last, end) = dfs(v)
                if last == 0:
                    continue
                book.append((end - last + 2, end + 1))
            book.sort()
            for (vs, ve) in book:
                if vs > e:
                    (s, e) = (ve - (ve - vs + 1 + e - s + 1) + 1, ve)
                else:
                    e += ve - vs + 1
            return (e - s + 1, e)
        print(dfs(ss.pop())[1] % MOD)

def input():
    return sys.stdin.readline().rstrip('\r\n')

def read_int_list():
    return list(map(int, input().split()))

def read_int_tuple():
    return tuple(map(int, input().split()))

def read_int():
    return int(input())
if __name__ == '__main__':
    main()

Solution (Python):
from functools import lru_cache as cache
from collections import Counter, defaultdict, deque
import math
import bisect
import string
from heapq import *
import sys

def get_int():
    return int(input())

def get_ints():
    return map(int, sys.stdin.readline().strip().split())

def get_list():
    return list(map(int, sys.stdin.readline().strip().split()))

def get_str():
    return sys.stdin.readline().strip()
MOD = 998244353

def main():
    testcases = get_int()
    for _ in range(testcases):
        (n, m) = get_ints()
        a = get_list()
        graph = [[] for _ in range(n)]
        indegree = [0 for _ in range(n)]
        for _ in range(m):
            (u, v) = get_ints()
            (u, v) = (u - 1, v - 1)
            graph[u].append(v)
            indegree[v] += 1
        print(solve(graph, indegree, n, a))

def merge_intervals(intervals):
    intervals.sort()
    merged_intervals = []
    for (start_time, size) in intervals:
        if not merged_intervals or start_time > merged_intervals[-1][0] + merged_intervals[-1][1]:
            merged_intervals.append([start_time, size])
        else:
            merged_intervals[-1][1] += size
            if merged_intervals[-1][1] >= MOD:
                merged_intervals[-1][1] = merged_intervals[-1][1] % MOD + MOD
    return merged_intervals

def solve(graph, indegree, n, a):
    q = deque()
    top_sorted = []
    result = 0
    for u in range(n):
        if indegree[u] == 0:
            q.append(u)
    while q:
        u = q.popleft()
        top_sorted.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)
    intervals = [[] for _ in range(n)]
    for u in range(n):
        if a[u] != 0:
            intervals[u].append([0, a[u]])
    for u in top_sorted:
        if len(intervals[u]) > 0:
            intervals[u] = merge_intervals(intervals[u])
            for v in graph[u]:
                for (start_time, size) in intervals[u]:
                    intervals[v].append([start_time + 1, size])
    last = top_sorted[-1]
    if len(intervals[last]) > 0:
        result = intervals[last][-1][1] + max(map(lambda e: e[0], intervals[last]))
    return result % MOD
if __name__ == '__main__':
    main()

Solution (Python):
import io, os
from collections import deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):

    def getnext(init, upnode):
        upnode.sort()
        output = []
        (currbegin, currend) = (0, 0)
        if init == 0 and (not upnode):
            return []
        if init > 0:
            currbegin = 1
            currend = init
        for [front, end] in upnode:
            if front > currend:
                if currbegin > 0:
                    output.append([currbegin, currend])
                currbegin = front + 1
                currend = end + 1
            else:
                currend += end - front + 1
        output.append([currbegin, currend])
        return output
    (n, m) = map(int, input().split())
    arr = list(map(int, input().split()))
    neigh = [[] for _ in range(n)]
    parentnum = [0] * n
    for _ in range(m):
        (u, v) = map(int, input().split())
        neigh[u - 1].append(v - 1)
        parentnum[v - 1] += 1
    if sum(arr) == 0:
        print(0)
        return
    queue = deque()
    for i in range(n):
        if parentnum[i] == 0:
            queue.append(i)
    states = [[] for _ in range(n)]
    while queue:
        index = queue.popleft()
        currstate = getnext(arr[index], states[index])
        for nextindex in neigh[index]:
            states[nextindex] += currstate
            parentnum[nextindex] -= 1
            if parentnum[nextindex] == 0:
                queue.append(nextindex)
    M = 998244353
    ans = currstate[-1][1] % M
    print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1