oj.uz

Submission #754071

# Submission time Handle Problem Language Result Execution time Memory
754071 2023-06-06T15:34:45 Z surojit Programming Contest (POI11_pro) Python 3
0 / 100
 362 ms 65536 KB 
from collections import deque

taskname = "A"
pb = deque.append
mp = lambda x, y: (x, y)

inf = int(1e6)
maxn = 505

class Edge:
    def __init__(self, u=None, v=None, c=None):
        self.u = u
        self.v = v
        self.c = c

e = [Edge() for _ in range(maxn * maxn * 2)]
adj = [[] for _ in range(maxn * 2)]
d = [0] * (maxn * 2)
trace = [-1] * (maxn * 2)
vis = [False] * (maxn * 2)
deg = [0] * maxn

def add_edge(u, v, c):
    global nTime
    e[nTime * 2] = Edge(u, v, c)
    e[nTime * 2 + 1] = Edge(v, u, 0)
    adj[u].append(nTime * 2)
    adj[v].append(nTime * 2 + 1)
    nTime += 1

def spfa():
    q = deque()
    for i in range(maxn * 2):
        d[i] = inf
        trace[i] = -1
        vis[i] = False

    q.append(s)
    d[s] = 0
    while q:
        u = q.popleft()
        vis[u] = False
        for c in adj[u]:
            if e[c].c > 0 and d[e[c].v] > 0:
                d[e[c].v] = 0
                trace[e[c].v] = c
                if not vis[e[c].v]:
                    vis[e[c].v] = True
                    q.append(e[c].v)

    return d[t] != inf

nTime = 0
n, m, R, T, K = map(int, input().split())
s, t = 0, n + m + 1
a = [None] * (maxn * maxn)
for i in range(1, K + 1):
    u, v = map(int, input().split())
    a[i] = mp(u, v)
    add_edge(u, v + n, 1)

for i in range(1, m + 1):
    add_edge(i + n, t, 1)

for i in range(1, n + 1):
    add_edge(s, i, 1)

res1 = 0
res = 0
for j in range(1, T // R + 1):
    for i in range(n):
        e[(i + K + m) * 2].c = 1
        e[(i + K + m) * 2 + 1].c = 0

    while spfa():
        delta = 1
        u = t
        while u != s:
            e[trace[u]].c -= delta
            e[trace[u] ^ 1].c += delta
            u = e[trace[u]].u

        res += j
        res1 += 1

print(res1, res * R)
for i in range(1, K + 1):
    if e[(i - 1) * 2].c == 0:
        print(a[i][0], a[i][1], R * deg[a[i][0]])
        deg[a[i][0]] += 1

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 316 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 311 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 330 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 321 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 338 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 352 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 337 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 362 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 338 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 349 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -