Submission #1148129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148129		ruben_ipenza	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	43 ms	10556 KiB

joi2019_ho_t4

import java.io.*;
import java.util.*;

public class joi2019_ho_t4 {
    static class Point {
        long x, y;

        Point(long x, long y) {
            this.x = x;
            this.y = y;
        }

        long manhattanDistance(Point other) {
            return Math.abs(x - other.x) + Math.abs(y - other.y);
        }
    }

    static class BipartiteMatching {
        private int n;
        private List<List<Edge>> graph;
        private int[] match;
        private boolean[] visited;

        static class Edge {
            int to;
            long cost;

            Edge(int to, long cost) {
                this.to = to;
                this.cost = cost;
            }
        }

        BipartiteMatching(int n) {
            this.n = n;
            this.graph = new ArrayList<>();
            for (int i = 0; i < n * 2; i++) {
                graph.add(new ArrayList<>());
            }
            this.match = new int[n * 2];
            this.visited = new boolean[n * 2];
        }

        void addEdge(int from, int to, long cost) {
            graph.get(from).add(new Edge(to + n, cost));
        }

        boolean dfs(int v, long threshold) {
            visited[v] = true;
            for (Edge e : graph.get(v)) {
                if (e.cost > threshold) continue;

                int u = e.to;
                int w = match[u];
                if (w < 0 || (!visited[w] && dfs(w, threshold))) {
                    match[v] = u;
                    match[u] = v;
                    return true;
                }
            }
            return false;
        }

        long minCostMatching() {
            Arrays.fill(match, -1);
            long low = 0;
            long high = 4000000000L;

            while (high - low > 1) {
                long mid = (low + high) / 2;
                if (isMatchingPossible(mid)) {
                    high = mid;
                } else {
                    low = mid;
                }
            }

            return high;
        }

        boolean isMatchingPossible(long threshold) {
            Arrays.fill(match, -1);

            boolean found;
            do {
                found = false;
                Arrays.fill(visited, false);

                for (int i = 0; i < n; i++) {
                    if (match[i] < 0 && !visited[i] && dfs(i, threshold)) {
                        found = true;
                    }
                }
            } while (found);

            for (int i = 0; i < n; i++) {
                if (match[i] < 0) return false;
            }
            return true;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());

        Point[] coins = new Point[2 * n];
        for (int i = 0; i < 2 * n; i++) {
            String[] parts = br.readLine().trim().split(" ");
            long x = Long.parseLong(parts[0]);
            long y = Long.parseLong(parts[1]);
            coins[i] = new Point(x, y);
        }

        BipartiteMatching matching = new BipartiteMatching(2 * n);

        // Create target positions
        Point[] targets = new Point[2 * n];
        int idx = 0;
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= 2; y++) {
                targets[idx++] = new Point(x, y);
            }
        }

        // Add edges between coins and target positions
        for (int i = 0; i < 2 * n; i++) {
            for (int j = 0; j < 2 * n; j++) {
                long dist = coins[i].manhattanDistance(targets[j]);
                matching.addEdge(i, j, dist);
            }
        }

        long result = matching.minCostMatching();
        System.out.println(result);
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63