oj.uz

답안 #328215

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
328215 2020-11-15T21:09:17 Z anishrajeev Mecho (IOI09_mecho) Java 11
50 / 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];
        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]));
            }
        }
        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, String[][] grid, int time, int startx, int starty, int homex, int homey, int N, int S){
        LinkedList<pair> q = new LinkedList<>();
        q.add(new pair(startx, starty, time*S));
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        boolean[][] visited = new boolean[N][N];
        while(!q.isEmpty()){
            pair p = q.poll();
            if(p.t >= bees[p.x][p.y])continue;
            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;
                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;
                q.add(new pair(nx, ny, p.t+1));
            }
        }
        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
50.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 8812 KB Output is correct
2 Correct 71 ms 8556 KB Output is correct
3 Correct 71 ms 8684 KB Output is correct
4 Correct 73 ms 8684 KB Output is correct
5 Correct 72 ms 8960 KB Output is correct
6 Correct 78 ms 8940 KB Output is correct
7 Runtime error 740 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Correct 77 ms 8684 KB Output is correct
9 Correct 82 ms 8920 KB Output is correct
10 Correct 80 ms 8812 KB Output is correct
11 Correct 79 ms 8808 KB Output is correct
12 Correct 117 ms 9732 KB Output is correct
13 Correct 125 ms 9836 KB Output is correct
14 Correct 227 ms 13980 KB Output is correct
15 Correct 81 ms 8812 KB Output is correct
16 Correct 81 ms 8812 KB Output is correct
17 Correct 92 ms 9088 KB Output is correct
18 Correct 93 ms 9196 KB Output is correct
19 Correct 98 ms 9276 KB Output is correct
20 Correct 97 ms 9196 KB Output is correct
21 Correct 106 ms 9692 KB Output is correct
22 Correct 107 ms 9452 KB Output is correct
23 Correct 116 ms 9832 KB Output is correct
24 Correct 148 ms 12136 KB Output is correct
25 Correct 140 ms 10072 KB Output is correct
26 Correct 159 ms 12100 KB Output is correct
27 Correct 142 ms 10220 KB Output is correct
28 Correct 195 ms 12820 KB Output is correct
29 Correct 175 ms 12484 KB Output is correct
30 Correct 213 ms 13756 KB Output is correct
31 Correct 187 ms 14080 KB Output is correct
32 Correct 181 ms 13588 KB Output is correct
33 Correct 639 ms 24320 KB Output is correct
34 Correct 690 ms 24784 KB Output is correct
35 Correct 837 ms 25484 KB Output is correct
36 Correct 577 ms 26948 KB Output is correct
37 Correct 659 ms 27072 KB Output is correct
38 Correct 909 ms 28168 KB Output is correct
39 Correct 666 ms 32872 KB Output is correct
40 Correct 769 ms 33232 KB Output is correct
41 Execution timed out 1096 ms 33792 KB Time limit exceeded
42 Correct 696 ms 36440 KB Output is correct
43 Correct 807 ms 37072 KB Output is correct
44 Execution timed out 1099 ms 37492 KB Time limit exceeded
45 Correct 780 ms 39396 KB Output is correct
46 Correct 832 ms 39444 KB Output is correct
47 Execution timed out 1098 ms 40436 KB Time limit exceeded
48 Correct 776 ms 47508 KB Output is correct
49 Correct 842 ms 43936 KB Output is correct
50 Execution timed out 1093 ms 49168 KB Time limit exceeded
51 Correct 837 ms 53896 KB Output is correct
52 Correct 919 ms 53872 KB Output is correct
53 Execution timed out 1105 ms 54756 KB Time limit exceeded
54 Correct 860 ms 59364 KB Output is correct
55 Correct 955 ms 59780 KB Output is correct
56 Execution timed out 1091 ms 60624 KB Time limit exceeded
57 Correct 885 ms 61324 KB Output is correct
58 Execution timed out 1032 ms 61920 KB Time limit exceeded
59 Execution timed out 1102 ms 62536 KB Time limit exceeded
60 Runtime error 675 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
61 Runtime error 696 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
62 Runtime error 665 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Runtime error 698 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
64 Runtime error 693 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
65 Runtime error 703 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
66 Runtime error 738 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
67 Runtime error 692 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
68 Runtime error 792 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Runtime error 796 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
70 Runtime error 803 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
71 Runtime error 798 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
72 Runtime error 790 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Runtime error 659 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 665 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 674 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 671 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 666 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 713 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 729 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 710 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 719 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 713 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 714 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 727 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Runtime error 731 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 679 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 723 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 724 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 719 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Runtime error 720 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
91 Runtime error 722 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 726 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)