oj.uz

Submission #328221

# Submission time Handle Problem Language Result Execution time Memory
328221 2020-11-15T21:41:13 Z anishrajeev Mecho (IOI09_mecho) Java 11
33 / 100
 1000 ms 25160 KB 
import java.io.*;
import java.util.*;

public class mecho {
    public static LinkedList<pair> q = new LinkedList<>();
    public static int[] dx = new int[]{0, 1, 0, -1};
    public static int[] dy = new int[]{1, 0, -1, 0};
    public static boolean[][] visited;
    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());
        char[][] grid = new char[N][N];
        int[][] bees = new int[N][N];
        visited = new boolean[N][N];
        int startx = 0, starty = 0, homex = 0, homey = 0;
        for(int i = 0; i < N; i++){
            String line = bf.readLine();
            Arrays.fill(bees[i], Integer.MAX_VALUE);
            for(int c = 0; c < N; c++){
                grid[i][c] = line.charAt(c);
                if(grid[i][c] == 'H'){
                    q.add(new pair(i, c, 0));
                    visited[i][c] = true;
                    bees[i][c] = 0;
                }
                if(grid[i][c] == 'M'){
                    startx = i;
                    starty = c;
                }
                if(grid[i][c]=='D'){
                    homex = i;
                    homey = c;
                }
            }
        }
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        while(!q.isEmpty()){
            pair p = q.pop();
            if(p.x == homex && p.y == homey)continue;
            if(grid[p.x][p.y] == 'T')continue;
            bees[p.x][p.y] = Math.min(bees[p.x][p.y], p.t+S);
            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 || visited[nx][ny])continue;
                q.add(new pair(nx, ny, bees[p.x][p.y]));
                visited[nx][ny] = true;

            }
        }
        bees[homex][homey] = Integer.MAX_VALUE;
        int start = 0, end = 1000000000;
        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;
        }
        if(!verify(bees, grid, 0, startx, starty, homex, homey, N, S))System.out.println(-1);
        else System.out.println(start);
    }
    public static boolean verify(int[][] bees, char[][] grid, int time, int startx, int starty, int homex, int homey, int N, int S){
        q.add(new pair(startx, starty, time*S));
        for(int i = 0; i < N; i++)Arrays.fill(visited[i], false);
        visited[startx][starty] = true;
        while(!q.isEmpty()){
            pair p = q.poll();
            if(p.t >= bees[p.x][p.y])continue;
            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(grid[nx][ny]=='T'||grid[nx][ny]=='H')continue;
                if(bees[nx][ny] <= p.t+1 || visited[nx][ny])continue;
                q.add(new pair(nx, ny, p.t+1));
                visited[nx][ny] = true;
            }
        }
        return visited[homex][homey];
    }
    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;
        }
    }
}

Subtask #1
33.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8556 KB Output is correct
2 Correct 70 ms 8556 KB Output is correct
3 Correct 72 ms 8556 KB Output is correct
4 Correct 73 ms 8556 KB Output is correct
5 Correct 72 ms 8596 KB Output is correct
6 Correct 72 ms 8556 KB Output is correct
7 Execution timed out 1094 ms 22516 KB Time limit exceeded
8 Correct 76 ms 8428 KB Output is correct
9 Incorrect 101 ms 10868 KB Output isn't correct
10 Correct 74 ms 8556 KB Output is correct
11 Correct 73 ms 8796 KB Output is correct
12 Correct 85 ms 8808 KB Output is correct
13 Correct 85 ms 8812 KB Output is correct
14 Correct 244 ms 13880 KB Output is correct
15 Correct 76 ms 8684 KB Output is correct
16 Incorrect 108 ms 11320 KB Output isn't correct
17 Correct 80 ms 8704 KB Output is correct
18 Incorrect 112 ms 11432 KB Output isn't correct
19 Correct 78 ms 8684 KB Output is correct
20 Incorrect 103 ms 11000 KB Output isn't correct
21 Correct 82 ms 8684 KB Output is correct
22 Incorrect 127 ms 11328 KB Output isn't correct
23 Correct 87 ms 8924 KB Output is correct
24 Incorrect 141 ms 12216 KB Output isn't correct
25 Correct 92 ms 9080 KB Output is correct
26 Incorrect 181 ms 13316 KB Output isn't correct
27 Correct 91 ms 8936 KB Output is correct
28 Incorrect 221 ms 13760 KB Output isn't correct
29 Correct 94 ms 8960 KB Output is correct
30 Incorrect 192 ms 13684 KB Output isn't correct
31 Correct 148 ms 12080 KB Output is correct
32 Incorrect 207 ms 13988 KB Output isn't correct
33 Correct 323 ms 15540 KB Output is correct
34 Incorrect 490 ms 15304 KB Output isn't correct
35 Incorrect 572 ms 15324 KB Output isn't correct
36 Correct 313 ms 15804 KB Output is correct
37 Incorrect 456 ms 15516 KB Output isn't correct
38 Incorrect 643 ms 15704 KB Output isn't correct
39 Correct 342 ms 16052 KB Output is correct
40 Incorrect 493 ms 15936 KB Output isn't correct
41 Incorrect 714 ms 16068 KB Output isn't correct
42 Correct 306 ms 16684 KB Output is correct
43 Incorrect 509 ms 16436 KB Output isn't correct
44 Incorrect 839 ms 16464 KB Output isn't correct
45 Correct 336 ms 17052 KB Output is correct
46 Incorrect 566 ms 16824 KB Output isn't correct
47 Incorrect 848 ms 17280 KB Output isn't correct
48 Correct 338 ms 17464 KB Output is correct
49 Incorrect 572 ms 17208 KB Output isn't correct
50 Execution timed out 1074 ms 17400 KB Time limit exceeded
51 Correct 356 ms 17824 KB Output is correct
52 Incorrect 531 ms 17668 KB Output isn't correct
53 Execution timed out 1092 ms 17736 KB Time limit exceeded
54 Correct 375 ms 18312 KB Output is correct
55 Incorrect 603 ms 18248 KB Output isn't correct
56 Execution timed out 1099 ms 18468 KB Time limit exceeded
57 Correct 352 ms 18796 KB Output is correct
58 Incorrect 652 ms 18740 KB Output isn't correct
59 Execution timed out 1087 ms 18900 KB Time limit exceeded
60 Correct 361 ms 19360 KB Output is correct
61 Incorrect 676 ms 19268 KB Output isn't correct
62 Execution timed out 1062 ms 19432 KB Time limit exceeded
63 Correct 506 ms 19220 KB Output is correct
64 Execution timed out 1090 ms 19220 KB Time limit exceeded
65 Correct 682 ms 19512 KB Output is correct
66 Correct 579 ms 19508 KB Output is correct
67 Correct 554 ms 19344 KB Output is correct
68 Execution timed out 1074 ms 19560 KB Time limit exceeded
69 Incorrect 977 ms 19604 KB Output isn't correct
70 Execution timed out 1096 ms 19348 KB Time limit exceeded
71 Execution timed out 1093 ms 19492 KB Time limit exceeded
72 Incorrect 956 ms 19388 KB Output isn't correct
73 Execution timed out 1092 ms 24748 KB Time limit exceeded
74 Execution timed out 1086 ms 24852 KB Time limit exceeded
75 Execution timed out 1089 ms 24852 KB Time limit exceeded
76 Execution timed out 1089 ms 24984 KB Time limit exceeded
77 Execution timed out 1091 ms 24792 KB Time limit exceeded
78 Execution timed out 1043 ms 24744 KB Time limit exceeded
79 Execution timed out 1097 ms 24772 KB Time limit exceeded
80 Execution timed out 1090 ms 25160 KB Time limit exceeded
81 Execution timed out 1050 ms 24992 KB Time limit exceeded
82 Execution timed out 1086 ms 24988 KB Time limit exceeded
83 Execution timed out 1056 ms 23992 KB Time limit exceeded
84 Execution timed out 1086 ms 24000 KB Time limit exceeded
85 Execution timed out 1088 ms 24116 KB Time limit exceeded
86 Execution timed out 1070 ms 24132 KB Time limit exceeded
87 Execution timed out 1063 ms 24000 KB Time limit exceeded
88 Execution timed out 1092 ms 23144 KB Time limit exceeded
89 Execution timed out 1066 ms 23076 KB Time limit exceeded
90 Execution timed out 1087 ms 23104 KB Time limit exceeded
91 Execution timed out 1077 ms 22992 KB Time limit exceeded
92 Execution timed out 1091 ms 23232 KB Time limit exceeded