oj.uz

Submission #754068

# Submission time Handle Problem Language Result Execution time Memory
754068 2023-06-06T15:27:11 Z shubhrajg Programming Contest (POI11_pro) PyPy 3
100 / 100
 458 ms 30580 KB 
from collections import defaultdict
import sys

# Read input values
num_workers, num_tasks, penalty_rate, total_time, num_avail_assign = map(int, sys.stdin.readline().split())

# Create an adjacency list to represent the graph
graph = defaultdict(list)

# Store the matching and degree arrays
matching = [-1] * num_tasks
degree = [0] * num_workers

# Array to track visited vertices during DFS
used = [0] * (num_workers + 1)

# Variable to track the current DFS iteration
T = 0

# Depth-first search function to find augmenting paths
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

# Read the edges of the graph and build the adjacency list
for _ in range(num_avail_assign):
    u, v = map(int, sys.stdin.readline().split())
    u -= 1
    v -= 1
    graph[u].append(v)

# Initialize the matching and degree arrays
for u in range(num_tasks):
    if matching[u] == -1:
        for v in range(num_workers):
            if u in graph[v] and matching[u] == -1:
                matching[u] = v
                degree[v] += 1

# Iterate until no more augmenting paths can be found
updated = True
while updated:
    ds = [(degree[v], v) for v in range(num_workers)]
    ds.sort()
    T += 1
    updated = any(try_dfs(v, degree[v]) for _, v in ds)

# Calculate penalty and collect the selected assignments
penalty = 0
res = []
for v in range(num_workers):
    degree[v] = min(degree[v], total_time // penalty_rate)

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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 21008 KB Output is correct
2 Correct 63 ms 20416 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 19240 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 21608 KB Output is correct
2 Correct 56 ms 18688 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 23192 KB Output is correct
2 Correct 113 ms 22908 KB Output is correct
3 Correct 56 ms 19440 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 27536 KB Output is correct
2 Correct 243 ms 27828 KB Output is correct
3 Correct 64 ms 19336 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 27788 KB Output is correct
2 Correct 220 ms 26500 KB Output is correct
3 Correct 91 ms 21800 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 28604 KB Output is correct
2 Correct 313 ms 27424 KB Output is correct
3 Correct 64 ms 19928 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 26876 KB Output is correct
2 Correct 285 ms 30580 KB Output is correct
3 Correct 296 ms 27732 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 28148 KB Output is correct
2 Correct 51 ms 19400 KB Output is correct
3 Correct 74 ms 20680 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 27168 KB Output is correct
2 Correct 362 ms 29336 KB Output is correct
3 Correct 189 ms 23108 KB Output is correct