oj.uz

Submission #764218

# Submission time Handle Problem Language Result Execution time Memory
764218 2023-06-23T08:47:43 Z rithikkatyal Programming Contest (POI11_pro) Python 3
0 / 100
 519 ms 6616 KB 
import sys
 
# Redirect stdin
#sys.stdin = open('contest.in', 'r')
 
# Redirect stdout
#sys.stdout = open('contest.out', 'w')

n, m, r, t, k = map(int, input().split())
graph ={}
matching = [-1] * m
degree = [0] * n
for i in range(n):
      if graph.get(i)==None:
        graph[i]=[]
                            
 
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
                            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):
                            degree[matching[u]]-=1
                            matching[u] = v
                            degree[v] += 1
                                        
 
 
penalty = 0
res = []
for v in range(n):
       b=(degree[v]*(2*3+(degree[v]-1)*3))//2
       while(b>t):
              degree[v]-=1
              b=(degree[v]*(2*3+(degree[v]-1)*3))//2
 
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))
res.sort(key=lambda x:(x[2],x[0]))        
print(len(res), penalty)
for el in res:
       print(el[0], el[1], el[2])

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 3116 KB It was possible to get penalty of 20418000 points and you received 20486060.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 2992 KB It was possible to get penalty of 55643980 points and you received 57233808.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 3024 KB It was possible to get penalty of 72329760 points and you received 73233882.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 3196 KB It was possible to get penalty of 5478600 points and you received 5533386.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 5584 KB Output is correct
2 Incorrect 435 ms 5636 KB It was possible to get penalty of 323502075 points and you received 323938650.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 441 ms 5076 KB It was possible to get penalty of 219191500 points and you received 219629883.
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 6616 KB Output is correct
2 Correct 293 ms 4388 KB Output is correct
3 Incorrect 15 ms 3120 KB It was possible to get penalty of 114794658 points and you received 114801159.
4 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 3664 KB Your program assigned 489 problems but it was possible to solve only 390.
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 457 ms 5148 KB It was possible to get penalty of 500 points and you received 501.
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 186 ms 3856 KB Your program assigned 458 problems but it was possible to solve only 452.
2 Halted 0 ms 0 KB -