# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
325443 |
2020-11-15T07:12:56 Z |
anishrajeev |
Mecho (IOI09_mecho) |
Java 11 |
|
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];
int counter = 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);
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]));
}
counter++;
}
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;
}
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){
Stack<pair> stack = new Stack<>();
stack.push(new pair(startx, starty, time*S));
int[] dx = new int[]{0, 1, 0, -1};
int[] dy = new int[]{1, 0, -1, 0};
TreeSet<pair> visited = new TreeSet<>();
while(!stack.isEmpty()){
pair p = stack.pop();
if(p.t >= bees[p.x][p.y])continue;
if(visited.contains(p))continue;
visited.add(p);
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;
stack.push(new pair(nx, ny, p.t+1));
}
}
for(pair p:visited){
if(p.x == homex && p.y == homey)return true;
}
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;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
8812 KB |
Output is correct |
2 |
Correct |
79 ms |
8668 KB |
Output is correct |
3 |
Correct |
77 ms |
8704 KB |
Output is correct |
4 |
Correct |
93 ms |
8952 KB |
Output is correct |
5 |
Correct |
78 ms |
8704 KB |
Output is correct |
6 |
Correct |
87 ms |
8812 KB |
Output is correct |
7 |
Runtime error |
831 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
8 |
Incorrect |
90 ms |
9000 KB |
Output isn't correct |
9 |
Correct |
208 ms |
12104 KB |
Output is correct |
10 |
Correct |
102 ms |
8944 KB |
Output is correct |
11 |
Correct |
108 ms |
9068 KB |
Output is correct |
12 |
Correct |
189 ms |
11116 KB |
Output is correct |
13 |
Correct |
132 ms |
9680 KB |
Output is correct |
14 |
Incorrect |
715 ms |
21168 KB |
Output isn't correct |
15 |
Correct |
115 ms |
8888 KB |
Output is correct |
16 |
Correct |
279 ms |
13196 KB |
Output is correct |
17 |
Correct |
331 ms |
13964 KB |
Output is correct |
18 |
Correct |
482 ms |
18292 KB |
Output is correct |
19 |
Correct |
351 ms |
13892 KB |
Output is correct |
20 |
Correct |
580 ms |
18692 KB |
Output is correct |
21 |
Correct |
379 ms |
14380 KB |
Output is correct |
22 |
Correct |
646 ms |
21324 KB |
Output is correct |
23 |
Correct |
591 ms |
21308 KB |
Output is correct |
24 |
Execution timed out |
1060 ms |
44312 KB |
Time limit exceeded |
25 |
Correct |
455 ms |
19460 KB |
Output is correct |
26 |
Execution timed out |
1094 ms |
44460 KB |
Time limit exceeded |
27 |
Correct |
755 ms |
25872 KB |
Output is correct |
28 |
Execution timed out |
1044 ms |
44188 KB |
Time limit exceeded |
29 |
Correct |
916 ms |
36904 KB |
Output is correct |
30 |
Execution timed out |
1065 ms |
38164 KB |
Time limit exceeded |
31 |
Correct |
602 ms |
18120 KB |
Output is correct |
32 |
Execution timed out |
1069 ms |
43380 KB |
Time limit exceeded |
33 |
Execution timed out |
1094 ms |
48732 KB |
Time limit exceeded |
34 |
Runtime error |
980 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
35 |
Execution timed out |
1054 ms |
41712 KB |
Time limit exceeded |
36 |
Execution timed out |
1067 ms |
46200 KB |
Time limit exceeded |
37 |
Execution timed out |
1091 ms |
44068 KB |
Time limit exceeded |
38 |
Execution timed out |
1051 ms |
46244 KB |
Time limit exceeded |
39 |
Execution timed out |
1078 ms |
52488 KB |
Time limit exceeded |
40 |
Execution timed out |
1087 ms |
65536 KB |
Time limit exceeded |
41 |
Execution timed out |
1056 ms |
61124 KB |
Time limit exceeded |
42 |
Execution timed out |
1049 ms |
42488 KB |
Time limit exceeded |
43 |
Execution timed out |
1028 ms |
65536 KB |
Time limit exceeded |
44 |
Execution timed out |
1081 ms |
65536 KB |
Time limit exceeded |
45 |
Execution timed out |
1068 ms |
47496 KB |
Time limit exceeded |
46 |
Execution timed out |
1004 ms |
65536 KB |
Time limit exceeded |
47 |
Execution timed out |
1089 ms |
64468 KB |
Time limit exceeded |
48 |
Execution timed out |
1075 ms |
52604 KB |
Time limit exceeded |
49 |
Execution timed out |
1049 ms |
53600 KB |
Time limit exceeded |
50 |
Execution timed out |
1012 ms |
65536 KB |
Time limit exceeded |
51 |
Execution timed out |
1029 ms |
59224 KB |
Time limit exceeded |
52 |
Execution timed out |
1043 ms |
65536 KB |
Time limit exceeded |
53 |
Execution timed out |
1037 ms |
65536 KB |
Time limit exceeded |
54 |
Execution timed out |
1032 ms |
59516 KB |
Time limit exceeded |
55 |
Execution timed out |
1074 ms |
65536 KB |
Time limit exceeded |
56 |
Execution timed out |
1068 ms |
65536 KB |
Time limit exceeded |
57 |
Execution timed out |
1075 ms |
62304 KB |
Time limit exceeded |
58 |
Runtime error |
997 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
59 |
Execution timed out |
1024 ms |
65536 KB |
Time limit exceeded |
60 |
Runtime error |
700 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
61 |
Runtime error |
886 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
62 |
Runtime error |
802 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
63 |
Runtime error |
744 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
64 |
Runtime error |
721 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
65 |
Runtime error |
727 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
66 |
Runtime error |
798 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
67 |
Runtime error |
768 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
68 |
Runtime error |
978 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
69 |
Runtime error |
886 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
70 |
Runtime error |
934 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
71 |
Execution timed out |
1006 ms |
65536 KB |
Time limit exceeded |
72 |
Runtime error |
951 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
73 |
Runtime error |
779 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
74 |
Runtime error |
689 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
75 |
Runtime error |
771 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
76 |
Runtime error |
740 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
77 |
Runtime error |
707 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
78 |
Runtime error |
818 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
79 |
Runtime error |
862 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
80 |
Runtime error |
791 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
81 |
Runtime error |
780 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
82 |
Runtime error |
753 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
83 |
Runtime error |
745 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
84 |
Runtime error |
850 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
85 |
Runtime error |
883 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
86 |
Runtime error |
934 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
87 |
Runtime error |
845 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
88 |
Runtime error |
748 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
89 |
Runtime error |
802 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
90 |
Runtime error |
910 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
91 |
Runtime error |
771 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
92 |
Runtime error |
857 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |