oj.uz

답안 #753958

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753958 2023-06-06T11:34:52 Z shubhrajg Programming Contest (POI11_pro) Python 3
40 / 100
 1000 ms 12064 KB 
from collections import defaultdict

n, m, r, t, k = map(int, input().split())

graph = defaultdict(list)
matching = [-1] * m
degree = [0] * n

used = [0] * (n + 1)
T = 0

def try_dfs(v, deg):
    global T
    if used[v] == T:
        return False
    used[v] = T
    if degree[v] > deg + 1:
        return True
    for u in graph[v]:
        if try_dfs(matching[u], deg):
            degree[matching[u]] -= 1
            matching[u] = v
            degree[v] += 1
            return True
    return False

for _ in range(k):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v)

for u in range(m):
    if matching[u] == -1:
        for v in range(n):
            if u in graph[v] and matching[u] == -1:
                matching[u] = v
                degree[v] += 1

updated = True
while updated:
    updated = False
    ds = [(degree[v], v) for v in range(n)]
    ds.sort()
    T += 1
    for _, v in ds:
        if try_dfs(v, degree[v]):
            updated = True
            break

penalty = 0
res = []
for v in range(n):
    degree[v] = min(degree[v], t // r)

for u in range(m):
    if matching[u] != -1 and degree[matching[u]]:
        penalty += degree[matching[u]] * r
        degree[matching[u]] -= 1
        res.append((matching[u] + 1, u + 1, degree[matching[u]] * r))

print(len(res), penalty)
for el in res:
    print(el[0], el[1], el[2])

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 3372 KB Output is correct
2 Correct 22 ms 3284 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 3348 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 3284 KB Output is correct
2 Correct 18 ms 3220 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 3672 KB Output is correct
2 Correct 206 ms 3700 KB Output is correct
3 Correct 20 ms 3348 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1077 ms 6604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1074 ms 6228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1070 ms 7776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 817 ms 4028 KB Output is correct
2 Execution timed out 1049 ms 6180 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1053 ms 6156 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 937 ms 4460 KB Output is correct
2 Execution timed out 1060 ms 12064 KB Time limit exceeded
3 Halted 0 ms 0 KB -