Submission #754071

#	Time	Username	Problem	Language	Result	Execution time	Memory
754071		surojit	Programming Contest (POI11_pro)	Cpython 3	0 / 100	362 ms	65536 KiB

pro

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10