oj.uz

Submission #328220

# Submission time Handle Problem Language Result Execution time Memory
328220 2020-11-15T21:36:23 Z anishrajeev Mecho (IOI09_mecho) Java 11
46 / 100
 1000 ms 25256 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 = 100000000;
        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
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 8428 KB Output is correct
2 Correct 71 ms 8684 KB Output is correct
3 Correct 70 ms 8556 KB Output is correct
4 Correct 73 ms 8664 KB Output is correct
5 Correct 73 ms 8556 KB Output is correct
6 Correct 72 ms 8556 KB Output is correct
7 Execution timed out 1093 ms 22360 KB Time limit exceeded
8 Correct 72 ms 8556 KB Output is correct
9 Correct 74 ms 8556 KB Output is correct
10 Correct 73 ms 8428 KB Output is correct
11 Correct 72 ms 8556 KB Output is correct
12 Correct 85 ms 8808 KB Output is correct
13 Correct 82 ms 8812 KB Output is correct
14 Correct 142 ms 11904 KB Output is correct
15 Correct 77 ms 8528 KB Output is correct
16 Correct 78 ms 8684 KB Output is correct
17 Correct 78 ms 8684 KB Output is correct
18 Correct 78 ms 8812 KB Output is correct
19 Correct 79 ms 8684 KB Output is correct
20 Correct 78 ms 8684 KB Output is correct
21 Correct 80 ms 8684 KB Output is correct
22 Correct 82 ms 8704 KB Output is correct
23 Correct 89 ms 9088 KB Output is correct
24 Correct 89 ms 8812 KB Output is correct
25 Correct 88 ms 8940 KB Output is correct
26 Correct 94 ms 8940 KB Output is correct
27 Correct 94 ms 8940 KB Output is correct
28 Correct 118 ms 10976 KB Output is correct
29 Correct 98 ms 8940 KB Output is correct
30 Correct 125 ms 12024 KB Output is correct
31 Correct 148 ms 12156 KB Output is correct
32 Correct 155 ms 12340 KB Output is correct
33 Correct 302 ms 15412 KB Output is correct
34 Incorrect 437 ms 15416 KB Output isn't correct
35 Incorrect 572 ms 15432 KB Output isn't correct
36 Correct 328 ms 16136 KB Output is correct
37 Incorrect 451 ms 15544 KB Output isn't correct
38 Incorrect 663 ms 15664 KB Output isn't correct
39 Correct 301 ms 16180 KB Output is correct
40 Incorrect 490 ms 15904 KB Output isn't correct
41 Incorrect 666 ms 16200 KB Output isn't correct
42 Correct 323 ms 16676 KB Output is correct
43 Incorrect 569 ms 16428 KB Output isn't correct
44 Incorrect 734 ms 16548 KB Output isn't correct
45 Correct 339 ms 16956 KB Output is correct
46 Incorrect 560 ms 16840 KB Output isn't correct
47 Incorrect 881 ms 17104 KB Output isn't correct
48 Correct 353 ms 17556 KB Output is correct
49 Incorrect 497 ms 17348 KB Output isn't correct
50 Incorrect 833 ms 17236 KB Output isn't correct
51 Correct 333 ms 17996 KB Output is correct
52 Incorrect 549 ms 17720 KB Output isn't correct
53 Incorrect 998 ms 17684 KB Output isn't correct
54 Correct 343 ms 18340 KB Output is correct
55 Incorrect 571 ms 18232 KB Output isn't correct
56 Execution timed out 1056 ms 18120 KB Time limit exceeded
57 Correct 355 ms 18988 KB Output is correct
58 Incorrect 567 ms 18616 KB Output isn't correct
59 Execution timed out 1042 ms 19016 KB Time limit exceeded
60 Correct 385 ms 19404 KB Output is correct
61 Incorrect 644 ms 19016 KB Output isn't correct
62 Execution timed out 1092 ms 19144 KB Time limit exceeded
63 Correct 508 ms 19220 KB Output is correct
64 Execution timed out 1090 ms 19304 KB Time limit exceeded
65 Correct 644 ms 19348 KB Output is correct
66 Correct 589 ms 19056 KB Output is correct
67 Correct 549 ms 19348 KB Output is correct
68 Correct 444 ms 19508 KB Output is correct
69 Execution timed out 1039 ms 19348 KB Time limit exceeded
70 Correct 425 ms 19528 KB Output is correct
71 Correct 425 ms 19480 KB Output is correct
72 Incorrect 880 ms 19584 KB Output isn't correct
73 Correct 426 ms 25052 KB Output is correct
74 Execution timed out 1068 ms 24852 KB Time limit exceeded
75 Correct 544 ms 25256 KB Output is correct
76 Correct 513 ms 24980 KB Output is correct
77 Correct 538 ms 25000 KB Output is correct
78 Correct 594 ms 25032 KB Output is correct
79 Execution timed out 1086 ms 25100 KB Time limit exceeded
80 Correct 613 ms 25000 KB Output is correct
81 Correct 593 ms 24760 KB Output is correct
82 Correct 554 ms 24932 KB Output is correct
83 Correct 593 ms 23892 KB Output is correct
84 Execution timed out 1100 ms 24076 KB Time limit exceeded
85 Correct 619 ms 24000 KB Output is correct
86 Correct 559 ms 23920 KB Output is correct
87 Execution timed out 1098 ms 24000 KB Time limit exceeded
88 Correct 601 ms 23276 KB Output is correct
89 Execution timed out 1100 ms 23104 KB Time limit exceeded
90 Execution timed out 1052 ms 23280 KB Time limit exceeded
91 Execution timed out 1090 ms 22932 KB Time limit exceeded
92 Correct 597 ms 23204 KB Output is correct