oj.uz

Submission #285774

# Submission time Handle Problem Language Result Execution time Memory
285774 2020-08-29T15:05:06 Z cprayer 개구리 (KOI13_frog) Java 11
12.32 / 22
 1000 ms 45404 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) {
            points.sort((o1, o2) -> {
                if (o1.y != o2.y) {
                    return Integer.compare(o1.y, o2.y);
                }
                return Integer.compare(o1.x, o2.x);
            });

            merge(points);

            for (int i = 0; i < points.size(); i++) {
                Point p = points.get(i);
                int t = p.x;
                p.x = p.y;
                p.y = t;
            }

            points.sort((o1, o2) -> {
                if (o1.y != o2.y) {
                    return Integer.compare(o1.y, o2.y);
                }
                return Integer.compare(o1.x, o2.x);
            });

            merge(points);

            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(List<Point> sorted) {

            TreeMap<Integer, Point> all = new TreeMap<>();

            int leftKey = 0;
            int leftVal = sorted.get(0).y;
            int length = sorted.size();
            for (int rightKey = 0; rightKey < length; rightKey++) {
                int rightVal = sorted.get(rightKey).y;
                while (leftVal + r < rightVal) {
                    Point deleted = sorted.get(leftKey);
                    all.remove(deleted.x, deleted);
                    leftKey += 1;
                    leftVal = sorted.get(leftKey).y;
                }

                Point point = sorted.get(rightKey);
                all.put(point.x, point);

                Map.Entry<Integer, Point> el = all.floorEntry(point.x - 1);
                Map.Entry<Integer, Point> er = all.ceilingEntry(point.x + 1);

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

                if (er != null && er.getValue().x <= point.x + r + d) {
                    merge(er.getValue().index, point.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

# Verdict Execution time Memory Grader output
1 Correct 221 ms 16484 KB Output is correct
2 Correct 226 ms 16372 KB Output is correct
3 Correct 224 ms 16112 KB Output is correct
4 Correct 206 ms 14060 KB Output is correct
5 Correct 245 ms 15636 KB Output is correct
6 Correct 279 ms 16468 KB Output is correct
7 Correct 231 ms 16128 KB Output is correct

Subtask #2
2.64 / 2.64

# Verdict Execution time Memory Grader output
1 Correct 234 ms 16880 KB Output is correct
2 Correct 255 ms 17136 KB Output is correct
3 Correct 264 ms 17128 KB Output is correct
4 Correct 259 ms 16504 KB Output is correct
5 Correct 239 ms 16624 KB Output is correct
6 Correct 267 ms 16896 KB Output is correct
7 Correct 250 ms 16780 KB Output is correct

Subtask #3
3.52 / 3.52

# Verdict Execution time Memory Grader output
1 Correct 238 ms 16684 KB Output is correct
2 Correct 224 ms 15964 KB Output is correct
3 Correct 261 ms 16752 KB Output is correct
4 Correct 258 ms 16368 KB Output is correct
5 Correct 277 ms 16760 KB Output is correct
6 Correct 273 ms 17384 KB Output is correct
7 Correct 362 ms 19148 KB Output is correct

Subtask #4
4.18 / 4.18

# Verdict Execution time Memory Grader output
1 Correct 384 ms 18856 KB Output is correct
2 Correct 520 ms 25488 KB Output is correct
3 Correct 459 ms 23220 KB Output is correct
4 Correct 459 ms 22348 KB Output is correct
5 Correct 500 ms 22360 KB Output is correct
6 Correct 560 ms 25360 KB Output is correct
7 Correct 524 ms 25300 KB Output is correct

Subtask #5
0 / 4.62

# Verdict Execution time Memory Grader output
1 Correct 370 ms 19000 KB Output is correct
2 Correct 365 ms 19152 KB Output is correct
3 Correct 458 ms 22728 KB Output is correct
4 Correct 487 ms 24096 KB Output is correct
5 Correct 847 ms 31972 KB Output is correct
6 Correct 745 ms 31572 KB Output is correct
7 Execution timed out 1129 ms 45404 KB Time limit exceeded

Subtask #6
0 / 5.06

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 44800 KB Time limit exceeded
2 Halted 0 ms 0 KB -