Submission #325443

# Submission time Handle Problem Language Result Execution time Memory
325443 2020-11-15T07:12:56 Z anishrajeev Mecho (IOI09_mecho) Java 11
33 / 100
1000 ms 65536 KB
import java.io.*;
import java.util.*;

public class mecho {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader bf = new BufferedReader(new FileReader("tester.in"));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(stk.nextToken());
        int S = Integer.parseInt(stk.nextToken());
        String[][] grid = new String[N][N];
        LinkedList<pair> list = new LinkedList<>();
        int[][] bees = new int[N][N];
        int startx = 0, starty = 0, homex = 0, homey = 0;
        for(int i = 0; i < N; i++){
            String line = bf.readLine();
            String[] str = line.split("");
            Arrays.fill(bees[i], Integer.MAX_VALUE);
            for(int c = 0; c < N; c++){
                grid[i][c] = str[c];
                if(grid[i][c].equals("H")){
                    list.add(new pair(i, c, 0));
                    bees[i][c] = 0;
                }
                if(grid[i][c].equals("M")){
                    startx = i;
                    starty = c;
                }
                if(grid[i][c].equals("D")){
                    homex = i;
                    homey = c;
                }
            }
        }
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        boolean[][] visited = new boolean[N][N];
        int counter = 0;
        while(!list.isEmpty()){
            pair p = list.pop();
            if(p.x == homex && p.y == homey)continue;
            if(grid[p.x][p.y].equals("T"))continue;
            bees[p.x][p.y] = Math.min(bees[p.x][p.y], p.t+S);
            if(visited[p.x][p.y])continue;
            visited[p.x][p.y] = true;
            for(int i = 0; i < 4; i++){
                int nx = p.x+dx[i];
                int ny = p.y+dy[i];
                if(N <= nx || nx < 0 || N <= ny || ny < 0)continue;
                list.add(new pair(nx, ny, bees[p.x][p.y]));
            }
            counter++;
        }
        bees[homex][homey] = Integer.MAX_VALUE;
        int start = 0, end = 10000000;
        while(start != end){
            int mid = (start+end+1)/2;
            if(verify(bees, grid, mid, startx, starty, homex, homey, N, S))start = mid;
            else end = mid-1;
        }
        System.out.println(start);
    }
    public static boolean verify(int[][] bees, String[][] grid, int time, int startx, int starty, int homex, int homey, int N, int S){
        Stack<pair> stack = new Stack<>();
        stack.push(new pair(startx, starty, time*S));
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        TreeSet<pair> visited = new TreeSet<>();
        while(!stack.isEmpty()){
            pair p = stack.pop();
            if(p.t >= bees[p.x][p.y])continue;
            if(visited.contains(p))continue;
            visited.add(p);
            for(int i = 0; i < 4; i++){
                int nx = p.x+dx[i];
                int ny = p.y+dy[i];
                if(N <= nx || nx < 0 || N <= ny || ny < 0)continue;
                if(bees[nx][ny] <= p.t)continue;
                if(grid[nx][ny].equals("T")||grid[nx][ny].equals("H"))continue;
                if(bees[nx][ny] <= p.t+1)continue;
                stack.push(new pair(nx, ny, p.t+1));
            }
        }
        for(pair p:visited){
            if(p.x == homex && p.y == homey)return true;
        }
        return false;
    }
    public static class pair implements Comparable<pair>{
        int x, y, t;
        public pair(int a, int b, int c){
            x = a;
            y = b;
            t = c;
        }

        @Override
        public int compareTo(pair o) {
            if(x==o.x&&y==o.y)return Integer.compare(t, o.t);
            if(x==o.x)return Integer.compare(y, o.y);
            return Integer.compare(x, o.x);
        }
        public boolean equals(pair o){
            if(x == o.x && y == o.y && t == o.t)return true;
            return false;
        }
    }
}
# Verdict Execution time Memory Grader output
1 Correct 77 ms 8812 KB Output is correct
2 Correct 79 ms 8668 KB Output is correct
3 Correct 77 ms 8704 KB Output is correct
4 Correct 93 ms 8952 KB Output is correct
5 Correct 78 ms 8704 KB Output is correct
6 Correct 87 ms 8812 KB Output is correct
7 Runtime error 831 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Incorrect 90 ms 9000 KB Output isn't correct
9 Correct 208 ms 12104 KB Output is correct
10 Correct 102 ms 8944 KB Output is correct
11 Correct 108 ms 9068 KB Output is correct
12 Correct 189 ms 11116 KB Output is correct
13 Correct 132 ms 9680 KB Output is correct
14 Incorrect 715 ms 21168 KB Output isn't correct
15 Correct 115 ms 8888 KB Output is correct
16 Correct 279 ms 13196 KB Output is correct
17 Correct 331 ms 13964 KB Output is correct
18 Correct 482 ms 18292 KB Output is correct
19 Correct 351 ms 13892 KB Output is correct
20 Correct 580 ms 18692 KB Output is correct
21 Correct 379 ms 14380 KB Output is correct
22 Correct 646 ms 21324 KB Output is correct
23 Correct 591 ms 21308 KB Output is correct
24 Execution timed out 1060 ms 44312 KB Time limit exceeded
25 Correct 455 ms 19460 KB Output is correct
26 Execution timed out 1094 ms 44460 KB Time limit exceeded
27 Correct 755 ms 25872 KB Output is correct
28 Execution timed out 1044 ms 44188 KB Time limit exceeded
29 Correct 916 ms 36904 KB Output is correct
30 Execution timed out 1065 ms 38164 KB Time limit exceeded
31 Correct 602 ms 18120 KB Output is correct
32 Execution timed out 1069 ms 43380 KB Time limit exceeded
33 Execution timed out 1094 ms 48732 KB Time limit exceeded
34 Runtime error 980 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Execution timed out 1054 ms 41712 KB Time limit exceeded
36 Execution timed out 1067 ms 46200 KB Time limit exceeded
37 Execution timed out 1091 ms 44068 KB Time limit exceeded
38 Execution timed out 1051 ms 46244 KB Time limit exceeded
39 Execution timed out 1078 ms 52488 KB Time limit exceeded
40 Execution timed out 1087 ms 65536 KB Time limit exceeded
41 Execution timed out 1056 ms 61124 KB Time limit exceeded
42 Execution timed out 1049 ms 42488 KB Time limit exceeded
43 Execution timed out 1028 ms 65536 KB Time limit exceeded
44 Execution timed out 1081 ms 65536 KB Time limit exceeded
45 Execution timed out 1068 ms 47496 KB Time limit exceeded
46 Execution timed out 1004 ms 65536 KB Time limit exceeded
47 Execution timed out 1089 ms 64468 KB Time limit exceeded
48 Execution timed out 1075 ms 52604 KB Time limit exceeded
49 Execution timed out 1049 ms 53600 KB Time limit exceeded
50 Execution timed out 1012 ms 65536 KB Time limit exceeded
51 Execution timed out 1029 ms 59224 KB Time limit exceeded
52 Execution timed out 1043 ms 65536 KB Time limit exceeded
53 Execution timed out 1037 ms 65536 KB Time limit exceeded
54 Execution timed out 1032 ms 59516 KB Time limit exceeded
55 Execution timed out 1074 ms 65536 KB Time limit exceeded
56 Execution timed out 1068 ms 65536 KB Time limit exceeded
57 Execution timed out 1075 ms 62304 KB Time limit exceeded
58 Runtime error 997 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
59 Execution timed out 1024 ms 65536 KB Time limit exceeded
60 Runtime error 700 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
61 Runtime error 886 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
62 Runtime error 802 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Runtime error 744 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
64 Runtime error 721 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
65 Runtime error 727 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
66 Runtime error 798 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
67 Runtime error 768 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
68 Runtime error 978 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Runtime error 886 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
70 Runtime error 934 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
71 Execution timed out 1006 ms 65536 KB Time limit exceeded
72 Runtime error 951 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Runtime error 779 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 689 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 771 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 740 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 707 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 818 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 862 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 791 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 780 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 753 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 745 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 850 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Runtime error 883 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 934 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 845 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 748 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 802 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Runtime error 910 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
91 Runtime error 771 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 857 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)