oj.uz

답안 #328217

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
328217 2020-11-15T21:20:21 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];
        boolean[][] visited = new boolean[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));
                    visited[i][c] = true;
                    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};
        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);
            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;
                list.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, 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];
        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].equals("T")||grid[nx][ny].equals("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;
            }
        }
        if(visited[homex][homey]){
            visited = null;
            return true;
        }
        else{
            visited = null;
            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;
        }
    }
}

Subtask #1
50.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 8824 KB Output is correct
2 Correct 74 ms 8680 KB Output is correct
3 Correct 72 ms 8556 KB Output is correct
4 Correct 73 ms 8556 KB Output is correct
5 Correct 75 ms 8668 KB Output is correct
6 Correct 76 ms 8668 KB Output is correct
7 Runtime error 771 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Correct 81 ms 8720 KB Output is correct
9 Correct 79 ms 8684 KB Output is correct
10 Correct 77 ms 8684 KB Output is correct
11 Correct 77 ms 8684 KB Output is correct
12 Correct 114 ms 9680 KB Output is correct
13 Correct 107 ms 9452 KB Output is correct
14 Correct 176 ms 11912 KB Output is correct
15 Correct 84 ms 8688 KB Output is correct
16 Correct 81 ms 8684 KB Output is correct
17 Correct 88 ms 9180 KB Output is correct
18 Correct 95 ms 9192 KB Output is correct
19 Correct 93 ms 9196 KB Output is correct
20 Correct 96 ms 9196 KB Output is correct
21 Correct 105 ms 9440 KB Output is correct
22 Correct 101 ms 9452 KB Output is correct
23 Correct 109 ms 9580 KB Output is correct
24 Correct 118 ms 9708 KB Output is correct
25 Correct 124 ms 9832 KB Output is correct
26 Correct 148 ms 11988 KB Output is correct
27 Correct 128 ms 9964 KB Output is correct
28 Correct 183 ms 12308 KB Output is correct
29 Correct 137 ms 9964 KB Output is correct
30 Correct 190 ms 12564 KB Output is correct
31 Correct 169 ms 11860 KB Output is correct
32 Correct 164 ms 12124 KB Output is correct
33 Correct 588 ms 24840 KB Output is correct
34 Correct 705 ms 24792 KB Output is correct
35 Correct 736 ms 25792 KB Output is correct
36 Correct 537 ms 26844 KB Output is correct
37 Correct 578 ms 27128 KB Output is correct
38 Correct 786 ms 28152 KB Output is correct
39 Correct 640 ms 32864 KB Output is correct
40 Correct 765 ms 33232 KB Output is correct
41 Execution timed out 1053 ms 33692 KB Time limit exceeded
42 Correct 674 ms 36780 KB Output is correct
43 Correct 761 ms 37448 KB Output is correct
44 Execution timed out 1047 ms 37724 KB Time limit exceeded
45 Correct 687 ms 39140 KB Output is correct
46 Correct 780 ms 39328 KB Output is correct
47 Execution timed out 1043 ms 40360 KB Time limit exceeded
48 Correct 726 ms 43520 KB Output is correct
49 Correct 791 ms 43840 KB Output is correct
50 Execution timed out 1096 ms 44780 KB Time limit exceeded
51 Correct 768 ms 53092 KB Output is correct
52 Correct 867 ms 53636 KB Output is correct
53 Execution timed out 1094 ms 54892 KB Time limit exceeded
54 Correct 787 ms 55832 KB Output is correct
55 Correct 873 ms 56532 KB Output is correct
56 Execution timed out 1055 ms 57584 KB Time limit exceeded
57 Correct 806 ms 61136 KB Output is correct
58 Correct 916 ms 61544 KB Output is correct
59 Execution timed out 1088 ms 62184 KB Time limit exceeded
60 Runtime error 662 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
61 Runtime error 698 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
62 Runtime error 656 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Runtime error 722 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
64 Runtime error 732 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
65 Runtime error 732 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
66 Runtime error 744 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
67 Runtime error 707 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
68 Runtime error 821 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Runtime error 822 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
70 Runtime error 833 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
71 Runtime error 836 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
72 Runtime error 829 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Runtime error 703 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 704 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 696 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 698 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 692 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 764 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 756 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 755 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 769 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 766 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 744 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 767 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Runtime error 759 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 702 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 760 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 755 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 752 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Runtime error 752 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
91 Runtime error 755 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 759 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)