| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 325573 |
2020-11-15T07:18:19 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];
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;
}
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));
}
}
stack = null;
dx = null;
dy = null;
for(pair p:visited){
if(p.x == homex && p.y == homey){
visited = null;
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 |
91 ms |
8576 KB |
Output is correct |
| 2 |
Correct |
82 ms |
8696 KB |
Output is correct |
| 3 |
Correct |
96 ms |
8808 KB |
Output is correct |
| 4 |
Correct |
102 ms |
8860 KB |
Output is correct |
| 5 |
Correct |
84 ms |
8832 KB |
Output is correct |
| 6 |
Correct |
101 ms |
8968 KB |
Output is correct |
| 7 |
Runtime error |
826 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Incorrect |
95 ms |
8956 KB |
Output isn't correct |
| 9 |
Correct |
201 ms |
11988 KB |
Output is correct |
| 10 |
Correct |
87 ms |
8788 KB |
Output is correct |
| 11 |
Correct |
115 ms |
9196 KB |
Output is correct |
| 12 |
Correct |
163 ms |
11068 KB |
Output is correct |
| 13 |
Correct |
145 ms |
9708 KB |
Output is correct |
| 14 |
Incorrect |
832 ms |
21172 KB |
Output isn't correct |
| 15 |
Correct |
134 ms |
9168 KB |
Output is correct |
| 16 |
Correct |
284 ms |
13428 KB |
Output is correct |
| 17 |
Correct |
355 ms |
13792 KB |
Output is correct |
| 18 |
Correct |
486 ms |
18224 KB |
Output is correct |
| 19 |
Correct |
386 ms |
13944 KB |
Output is correct |
| 20 |
Correct |
698 ms |
18812 KB |
Output is correct |
| 21 |
Correct |
358 ms |
14396 KB |
Output is correct |
| 22 |
Correct |
679 ms |
21204 KB |
Output is correct |
| 23 |
Correct |
659 ms |
21036 KB |
Output is correct |
| 24 |
Execution timed out |
1037 ms |
44420 KB |
Time limit exceeded |
| 25 |
Correct |
427 ms |
19480 KB |
Output is correct |
| 26 |
Execution timed out |
1041 ms |
44252 KB |
Time limit exceeded |
| 27 |
Correct |
715 ms |
25844 KB |
Output is correct |
| 28 |
Execution timed out |
1089 ms |
44348 KB |
Time limit exceeded |
| 29 |
Correct |
912 ms |
36852 KB |
Output is correct |
| 30 |
Execution timed out |
1081 ms |
45156 KB |
Time limit exceeded |
| 31 |
Correct |
560 ms |
18064 KB |
Output is correct |
| 32 |
Execution timed out |
1059 ms |
43344 KB |
Time limit exceeded |
| 33 |
Execution timed out |
1055 ms |
48448 KB |
Time limit exceeded |
| 34 |
Execution timed out |
1079 ms |
65536 KB |
Time limit exceeded |
| 35 |
Execution timed out |
1068 ms |
41424 KB |
Time limit exceeded |
| 36 |
Execution timed out |
1090 ms |
48028 KB |
Time limit exceeded |
| 37 |
Execution timed out |
1093 ms |
44020 KB |
Time limit exceeded |
| 38 |
Execution timed out |
1057 ms |
46080 KB |
Time limit exceeded |
| 39 |
Execution timed out |
1094 ms |
46564 KB |
Time limit exceeded |
| 40 |
Execution timed out |
1053 ms |
65076 KB |
Time limit exceeded |
| 41 |
Execution timed out |
1059 ms |
65536 KB |
Time limit exceeded |
| 42 |
Execution timed out |
1044 ms |
48172 KB |
Time limit exceeded |
| 43 |
Execution timed out |
1067 ms |
65536 KB |
Time limit exceeded |
| 44 |
Runtime error |
965 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 45 |
Execution timed out |
1093 ms |
53504 KB |
Time limit exceeded |
| 46 |
Execution timed out |
1029 ms |
65536 KB |
Time limit exceeded |
| 47 |
Execution timed out |
1053 ms |
58292 KB |
Time limit exceeded |
| 48 |
Execution timed out |
1012 ms |
47192 KB |
Time limit exceeded |
| 49 |
Execution timed out |
1108 ms |
56500 KB |
Time limit exceeded |
| 50 |
Execution timed out |
1014 ms |
65536 KB |
Time limit exceeded |
| 51 |
Execution timed out |
1089 ms |
58812 KB |
Time limit exceeded |
| 52 |
Execution timed out |
1050 ms |
65536 KB |
Time limit exceeded |
| 53 |
Runtime error |
998 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 54 |
Execution timed out |
1024 ms |
59196 KB |
Time limit exceeded |
| 55 |
Execution timed out |
1049 ms |
65536 KB |
Time limit exceeded |
| 56 |
Execution timed out |
1037 ms |
65536 KB |
Time limit exceeded |
| 57 |
Execution timed out |
1032 ms |
65536 KB |
Time limit exceeded |
| 58 |
Execution timed out |
1068 ms |
65536 KB |
Time limit exceeded |
| 59 |
Execution timed out |
1028 ms |
65536 KB |
Time limit exceeded |
| 60 |
Runtime error |
710 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 61 |
Runtime error |
781 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 62 |
Runtime error |
714 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 63 |
Runtime error |
854 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 64 |
Runtime error |
788 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 65 |
Runtime error |
725 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 66 |
Runtime error |
784 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 67 |
Runtime error |
743 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 68 |
Runtime error |
890 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 69 |
Execution timed out |
1037 ms |
65536 KB |
Time limit exceeded |
| 70 |
Runtime error |
952 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 71 |
Execution timed out |
1004 ms |
65536 KB |
Time limit exceeded |
| 72 |
Runtime error |
839 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 73 |
Runtime error |
761 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 74 |
Runtime error |
745 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 75 |
Runtime error |
761 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 76 |
Runtime error |
782 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 77 |
Runtime error |
739 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 78 |
Runtime error |
733 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 79 |
Runtime error |
759 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 80 |
Runtime error |
781 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 81 |
Runtime error |
773 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 82 |
Runtime error |
846 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 83 |
Runtime error |
886 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 84 |
Runtime error |
821 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 85 |
Runtime error |
796 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 86 |
Runtime error |
707 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 87 |
Runtime error |
800 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 88 |
Runtime error |
879 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 89 |
Runtime error |
913 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 90 |
Runtime error |
856 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 91 |
Runtime error |
800 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 92 |
Runtime error |
821 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
