Submission #6036830


Source Code Expand

Copy
from scipy.sparse.csgraph import dijkstra
# 二部グラフ完全マッチング
# 最大フロー
N = int(input())
NN = N * 2
XY = [[int(x) for x in input().split()] for _ in range(NN)]
graph = [[0] * (NN+2) for _ in range(NN+2)]
start = NN
goal = NN+1

for i,(a,b) in enumerate(XY[:N]):
  for j,(c,d) in enumerate(XY[N:], N):
    if a < c and b < d:
      graph[i][j] = 1

for i in range(N):
  graph[start][i] = 1
for i in range(N,NN):
  graph[i][goal] = 1
  
INF = 10 ** 9

def max_flow(graph):
  dist, pred = dijkstra(graph, indices = start, return_predecessors = True)
  if dist[goal] > INF:
    return 0
  y = goal
  while y != start:
    x = pred[y]
    graph[x][y] -= 1
    graph[y][x] += 1
    y = x
  return 1 + max_flow(graph)

answer = max_flow(graph)
print(answer)

Submission Info

Submission Time
Task C - 2D Plane 2N Points
User maspy
Language Python (3.4.3)
Score 400
Code Size 812 Byte
Status AC
Exec Time 552 ms
Memory 15132 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 5
AC × 17
Set Name Test Cases
Sample example_0, example_1, example_2, example_3, example_4
All example_0, example_1, example_2, example_3, example_4, line_0, line_1, line_2, line_3, maxrand_0, maxrand_1, maxrand_2, maxrand_3, maxrand_4, rand_0, rand_1, rand_2
Case Name Status Exec Time Memory
example_0 AC 167 ms 13632 KB
example_1 AC 169 ms 13644 KB
example_2 AC 166 ms 13636 KB
example_3 AC 170 ms 13644 KB
example_4 AC 169 ms 13640 KB
line_0 AC 215 ms 14020 KB
line_1 AC 173 ms 14524 KB
line_2 AC 169 ms 14016 KB
line_3 AC 167 ms 13768 KB
maxrand_0 AC 509 ms 14996 KB
maxrand_1 AC 511 ms 15124 KB
maxrand_2 AC 501 ms 15124 KB
maxrand_3 AC 552 ms 15132 KB
maxrand_4 AC 483 ms 15000 KB
rand_0 AC 494 ms 14996 KB
rand_1 AC 246 ms 14272 KB
rand_2 AC 298 ms 14524 KB