Submission #764084

# Submission time Handle Problem Language Result Execution time Memory
764084 2023-06-23T07:00:00 Z rithikkatyal Programming Contest (POI11_pro) Python 3
0 / 100
547 ms 6468 KB
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 -