제출 #285765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285765		cprayer	개구리 (KOI13_frog)	Java	1.98 / 22	1220 ms	262148 KiB

frog

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class frog {

    public static void main(String[] args) {
        Problems problems = new Problems();
        problems.solve();
    }
}

class Problems {

    Parser parser = new Parser();

    void solve() {
        int t = 1;
        for (int i = 0; i < t; i++) {

            Problem problem = new Problem();
            problem.solve(i);
        }
    }

    class Problem {

        int N;
        int r;
        int d;
        int[] f;
        List<Point> points = new ArrayList<>();

        public Problem() {
            N = parser.parseInt();
            r = parser.parseInt();

            points.add(new Point(0, 0, 0));
            for (int i = 1; i <= N; i++) {
                int x = parser.parseInt();
                int y = parser.parseInt();
                if(x == 0 && y == 0) {
                    continue;
                }
                points.add(new Point(x, y, i));
            }

            d = parser.parseInt();
            f = new int[N + 1];
            for(int i = 0; i <= N; i++) {
                f[i] = i;
            }
        }

        void solve(int testCase) {
            Map<Integer, List<Point>> sorted = new TreeMap<>();
            for (int i = 0; i < points.size(); i++) {
                Point p = points.get(i);
                sorted.computeIfAbsent(p.y, ArrayList::new).add(p);
            }

            merge(sorted);
            sorted.clear();

            for (int i = 0; i < points.size(); i++) {
                Point p = points.get(i);
                int t = p.x;
                p.x = p.y;
                p.y = t;
                sorted.computeIfAbsent(p.y, ArrayList::new).add(p);
            }

            merge(sorted);

            int ans = 0;

            for(int i = 0; i < points.size(); i++) {
                Point p = points.get(i);
                if(find(p.index) == 0) {
                    ans = Math.max(ans, p.x + p.y + 2 * r);
                }
            }

            System.out.println(ans);
        }

        void merge(Map<Integer, List<Point>> sorted) {

            TreeMap<Integer, Point> all = new TreeMap<>();
            List<Integer> keys = new ArrayList<>(sorted.keySet());

            int leftKey = 0;
            int leftVal = keys.get(0);
            for(int rightKey = 0; rightKey < keys.size(); rightKey++) {
                int rightVal = keys.get(rightKey);
                while (leftVal + r < rightVal) {

                    for (Point deleted : sorted.get(leftVal)) {
                        all.remove(deleted.x, deleted);
                    }
                    leftKey += 1;
                    leftVal = keys.get(leftKey);
                }

                for (Point p : sorted.get(rightVal)) {
                    all.put(p.x, p);
                }

                Point previous = null;
                for (Point p : all.values()) {
                    if(previous == null) {
                        previous = p;
                        continue;
                    }

                    if(p.x <= previous.x + r + d) {
                        merge(p.index, previous.index);
                    }

                    previous = p;
                }
            }
        }

        void merge(int a, int b) {
            a = find(a);
            b = find(b);

            if (a == b) {
                return;
            }

            if (a > b) {
                int t = a;
                a = b;
                b = t;
            }

            f[b] = a;
        }

        int find(int v) {
            return f[v] == v ? v : (f[v] = find(f[v]));
        }

        class Point {
            int x, y, index;

            public Point(int x, int y, int index) {
                this.x = x;
                this.y = y;
                this.index = index;
            }
        }

    }

}

class Parser {
    private final Iterator<String> stringIterator;
    private final Deque<String> inputs;

    Parser() {
        this(System.in);
    }

    Parser(InputStream in) {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        stringIterator = br.lines().iterator();
        inputs = new ArrayDeque<>();
    }

    void fill() {
        while (inputs.isEmpty()) {
            if (!stringIterator.hasNext()) throw new NoSuchElementException();
            inputs.addAll(Arrays.asList(stringIterator.next().split(" ")));
            while (!inputs.isEmpty() && inputs.getFirst().isEmpty()) {
                inputs.removeFirst();
            }
        }
    }

    Integer parseInt() {
        fill();
        if (!inputs.isEmpty()) {
            return Integer.parseInt(inputs.pollFirst());
        }
        throw new NoSuchElementException();
    }

    Long parseLong() {
        fill();
        if (!inputs.isEmpty()) {
            return Long.parseLong(inputs.pollFirst());
        }
        throw new NoSuchElementException();
    }

    Double parseDouble() {
        fill();
        if (!inputs.isEmpty()) {
            return Double.parseDouble(inputs.pollFirst());
        }
        throw new NoSuchElementException();
    }

    String parseString() {
        fill();
        return inputs.removeFirst();
    }
}

• Subtask 1: 1.98 / 1.98
• Subtask 2: 0 / 2.64
• Subtask 3: 0 / 3.52
• Subtask 4: 0 / 4.18
• Subtask 5: 0 / 4.62
• Subtask 6: 0 / 5.06