n, m, r, t, k = map(int, input().split())
# graph = defaultdict(list)
graph ={}
matching = [-1] * m
degree = [0] * n
for i in range(n):
if graph.get(i)==None:
graph[i]=[]
# 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
# def find(d,matching,degree):
# for u in range(m):
# if matching[u] == -1:
# for v in range(d,n):
# if u in graph[v] and matching[u] == -1:
# matching[u] = v
# degree[v] += 1
# if v<n-1:
# find(v+1,matching,degree)
# else:
# return 0
for _ in range(k):
u, v = map(int, input().split())
u -= 1
v -= 1
graph[u].append(v)
#find(0,matching,degree)
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
break
for u in range(m):
if matching[u] != -1:
for v in range(n):
if u in graph[v] and matching[u] !=v and degree[matching[u]]>(degree[v]+1):
# print(matching[u],v,u,"ans")
# print(degree[matching[u]]-1,degree[v]+1,u,"ans12")
degree[matching[u]]-=1
matching[u] = v
degree[v] += 1
#print(degree[matching[u]],degree[v],u,"ans12")
# updated = True
# while updated:
# ds = [(degree[v], v) for v in range(n)]
# ds.sort()
# T += 1
# updated = any(try_dfs(v, degree[v]) for _, v in ds)
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]]:
# print(matching[u],degree[matching[u]])
penalty += degree[matching[u]] * r
degree[matching[u]] -= 1
res.append((matching[u] + 1, u + 1, degree[matching[u]] * r))
res.sort(key=lambda x:(x[2],x[0]))
print(len(res), penalty)
for el in res:
print(el[0], el[1], el[2])
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
3020 KB |
It was possible to get penalty of 20418000 points and you received 20486060. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
2976 KB |
It was possible to solve 95 problems and you solved only 91. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
2988 KB |
It was possible to solve 80 problems and you solved only 79. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
3068 KB |
It was possible to get penalty of 5478600 points and you received 5533386. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
480 ms |
5436 KB |
Output is correct |
| 2 |
Incorrect |
441 ms |
6132 KB |
It was possible to solve 494 problems and you solved only 493. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
446 ms |
4920 KB |
It was possible to get penalty of 219191500 points and you received 219629883. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
547 ms |
6468 KB |
Output is correct |
| 2 |
Correct |
302 ms |
4592 KB |
Output is correct |
| 3 |
Incorrect |
19 ms |
3108 KB |
It was possible to get penalty of 114794658 points and you received 114801159. |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
3552 KB |
It was possible to get penalty of 68704815 points and you received 68805114. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
464 ms |
5032 KB |
It was possible to get penalty of 500 points and you received 501. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
196 ms |
3660 KB |
It was possible to solve 452 problems and you solved only 451. |
| 2 |
Halted |
0 ms |
0 KB |
- |
