oj.uz

Submission #328219

# Submission time Handle Problem Language Result Execution time Memory
328219 2020-11-15T21:33:56 Z anishrajeev Mecho (IOI09_mecho) Java 11
57 / 100
 1000 ms 25700 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 = 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;
        }
        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
57.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8556 KB Output is correct
2 Correct 72 ms 8556 KB Output is correct
3 Correct 77 ms 8576 KB Output is correct
4 Correct 72 ms 8428 KB Output is correct
5 Correct 74 ms 8684 KB Output is correct
6 Correct 71 ms 8556 KB Output is correct
7 Correct 647 ms 23276 KB Output is correct
8 Correct 80 ms 8556 KB Output is correct
9 Correct 72 ms 8424 KB Output is correct
10 Correct 91 ms 8616 KB Output is correct
11 Correct 75 ms 8556 KB Output is correct
12 Correct 86 ms 8940 KB Output is correct
13 Correct 82 ms 8812 KB Output is correct
14 Correct 140 ms 11696 KB Output is correct
15 Correct 75 ms 8832 KB Output is correct
16 Correct 76 ms 8684 KB Output is correct
17 Correct 75 ms 8684 KB Output is correct
18 Correct 75 ms 8684 KB Output is correct
19 Correct 76 ms 8684 KB Output is correct
20 Correct 80 ms 8684 KB Output is correct
21 Correct 82 ms 8596 KB Output is correct
22 Correct 81 ms 8684 KB Output is correct
23 Correct 85 ms 8812 KB Output is correct
24 Correct 116 ms 11492 KB Output is correct
25 Correct 90 ms 8812 KB Output is correct
26 Correct 123 ms 12024 KB Output is correct
27 Correct 92 ms 8936 KB Output is correct
28 Correct 128 ms 12040 KB Output is correct
29 Correct 126 ms 12012 KB Output is correct
30 Correct 153 ms 12232 KB Output is correct
31 Correct 114 ms 10928 KB Output is correct
32 Correct 132 ms 12104 KB Output is correct
33 Correct 336 ms 15328 KB Output is correct
34 Correct 385 ms 15308 KB Output is correct
35 Correct 411 ms 15444 KB Output is correct
36 Correct 343 ms 15808 KB Output is correct
37 Correct 358 ms 15812 KB Output is correct
38 Correct 450 ms 15832 KB Output is correct
39 Correct 354 ms 15840 KB Output is correct
40 Correct 423 ms 15688 KB Output is correct
41 Incorrect 674 ms 15944 KB Output isn't correct
42 Correct 365 ms 16876 KB Output is correct
43 Correct 389 ms 16720 KB Output is correct
44 Incorrect 776 ms 16436 KB Output isn't correct
45 Correct 344 ms 17092 KB Output is correct
46 Correct 405 ms 17108 KB Output is correct
47 Incorrect 831 ms 16968 KB Output isn't correct
48 Correct 369 ms 17476 KB Output is correct
49 Correct 388 ms 17620 KB Output is correct
50 Incorrect 851 ms 17196 KB Output isn't correct
51 Correct 381 ms 17888 KB Output is correct
52 Correct 404 ms 17840 KB Output is correct
53 Incorrect 913 ms 17736 KB Output isn't correct
54 Correct 357 ms 18356 KB Output is correct
55 Correct 411 ms 18388 KB Output is correct
56 Incorrect 985 ms 18120 KB Output isn't correct
57 Correct 366 ms 18868 KB Output is correct
58 Correct 429 ms 18980 KB Output is correct
59 Execution timed out 1080 ms 18896 KB Time limit exceeded
60 Correct 402 ms 20056 KB Output is correct
61 Correct 425 ms 19796 KB Output is correct
62 Execution timed out 1090 ms 19984 KB Time limit exceeded
63 Correct 710 ms 19580 KB Output is correct
64 Execution timed out 1066 ms 19880 KB Time limit exceeded
65 Correct 851 ms 20000 KB Output is correct
66 Correct 807 ms 20172 KB Output is correct
67 Correct 725 ms 19856 KB Output is correct
68 Correct 449 ms 20028 KB Output is correct
69 Correct 468 ms 20272 KB Output is correct
70 Correct 430 ms 20116 KB Output is correct
71 Correct 424 ms 20116 KB Output is correct
72 Correct 414 ms 20028 KB Output is correct
73 Correct 419 ms 25700 KB Output is correct
74 Execution timed out 1093 ms 25364 KB Time limit exceeded
75 Correct 544 ms 25680 KB Output is correct
76 Correct 521 ms 25592 KB Output is correct
77 Correct 518 ms 25620 KB Output is correct
78 Correct 598 ms 25412 KB Output is correct
79 Execution timed out 1088 ms 25464 KB Time limit exceeded
80 Correct 581 ms 25476 KB Output is correct
81 Correct 576 ms 25412 KB Output is correct
82 Correct 564 ms 25412 KB Output is correct
83 Correct 595 ms 24384 KB Output is correct
84 Execution timed out 1095 ms 24524 KB Time limit exceeded
85 Correct 608 ms 24768 KB Output is correct
86 Correct 555 ms 24708 KB Output is correct
87 Correct 580 ms 24512 KB Output is correct
88 Correct 608 ms 23744 KB Output is correct
89 Execution timed out 1078 ms 23988 KB Time limit exceeded
90 Correct 619 ms 23744 KB Output is correct
91 Correct 622 ms 23704 KB Output is correct
92 Correct 610 ms 23772 KB Output is correct