oj.uz

Submission #285765

# Submission time Handle Problem Language Result Execution time Memory
285765 2020-08-29T14:55:23 Z cprayer 개구리 (KOI13_frog) Java 11
1.98 / 22
 1000 ms 262148 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<>();
            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

# Verdict Execution time Memory Grader output
1 Correct 224 ms 17192 KB Output is correct
2 Correct 224 ms 17292 KB Output is correct
3 Correct 240 ms 16500 KB Output is correct
4 Correct 211 ms 18308 KB Output is correct
5 Correct 230 ms 17552 KB Output is correct
6 Correct 248 ms 34176 KB Output is correct
7 Correct 239 ms 22768 KB Output is correct

Subtask #2
0 / 2.64

# Verdict Execution time Memory Grader output
1 Correct 648 ms 140896 KB Output is correct
2 Correct 300 ms 41992 KB Output is correct
3 Runtime error 914 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 3.52

# Verdict Execution time Memory Grader output
1 Correct 266 ms 41660 KB Output is correct
2 Runtime error 956 ms 262148 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 4.18

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

Subtask #5
0 / 4.62

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

Subtask #6
0 / 5.06

# Verdict Execution time Memory Grader output
1 Runtime error 820 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -