oj.uz

답안 #285746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
285746 2020-08-29T14:24:21 Z cprayer 개구리 (KOI13_frog) Java 11
1.98 / 22
 1000 ms 262152 KB 
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<>();
            Iterator<Integer> leftKey = sorted.keySet().iterator();
            int leftVal = leftKey.next();
            for (int rightKey : sorted.keySet()) {
                while (leftVal + r < rightKey) {

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

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

                for (Point p : sorted.get(rightKey)) {
                    Map.Entry<Integer, Point> el = all.floorEntry(p.x - 1);
                    Map.Entry<Integer, Point> er = all.ceilingEntry(p.x + 1);

                    if (el != null && p.x <= el.getValue().x + r + d) {
                        merge(el.getValue().index, p.index);
                    }

                    if (er != null && er.getValue().x <= p.x + r + d) {
                        merge(er.getValue().index, p.index);
                    }
                }
            }
        }

        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

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 16480 KB Output is correct
2 Correct 234 ms 17120 KB Output is correct
3 Correct 235 ms 16404 KB Output is correct
4 Correct 232 ms 18968 KB Output is correct
5 Correct 242 ms 16888 KB Output is correct
6 Correct 261 ms 34144 KB Output is correct
7 Correct 277 ms 23072 KB Output is correct

Subtask #2
0 / 2.64

# 결과 실행 시간 메모리 Grader output
1 Correct 423 ms 118344 KB Output is correct
2 Correct 299 ms 41248 KB Output is correct
3 Runtime error 859 ms 262152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 3.52

# 결과 실행 시간 메모리 Grader output
1 Correct 272 ms 40956 KB Output is correct
2 Runtime error 1135 ms 262152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 4.18

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1350 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.62

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1112 ms 262152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.06

# 결과 실행 시간 메모리 Grader output
1 Runtime error 784 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -