oj.uz

Submission #255337

# Submission time Handle Problem Language Result Execution time Memory
255337 2020-07-31T17:39:49 Z model_code Firefighting (NOI20_firefighting) Python 3
0 / 100
 48 ms 4612 KB 
import sys
import threading
sys.setrecursionlimit(1000000)
threading.stack_size(1<<27)
class Work:
    def __call__(self):
        (N, K) = [int(x) for x in sys.stdin.readline().split()]
        adjlist = [[] for _ in range(N)]
        for line in sys.stdin.readlines():
            (A, B, W) = [int(x) for x in line.split()]
            A -= 1
            B -= 1
            adjlist[A].append((B, W))
            adjlist[B].append((A, W))
        ans = []
        def dfs(index, prev, dist):
            max_overflow = -1<<62
            max_underflow = 0;
            for (target, length) in adjlist[index]:
                if target != prev:
                    (type, val) = dfs(target, index, length)
                    if type:
                        if max_overflow < val:
                            max_overflow = val
                    else:
                        if max_underflow < val:
                            max_underflow = val
            if max_overflow >= max_underflow:
                ret = (True, max_overflow - dist)
            else:
                ret = (False, max_underflow + dist)
            if (not ret[0]) and (ret[1] > K):
                ans.append(index)
                ret = (True, K - dist)
            if ret[0] and (ret[1] < 0):
                ret = (False, 0)
            return ret
        dfs(0, -1, 1<<60)
        sys.stdout.write(str(len(ans)) + '\n' + ' '.join([str(x + 1) for x in ans]))
t = threading.Thread(target=Work())
t.start()
t.join()

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 4612 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 4484 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 4484 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 4588 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 4484 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 4492 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -