oj.uz

Submission #584747

# Submission time Handle Problem Language Result Execution time Memory
584747 2022-06-28T01:26:52 Z PikaChu999 Mecho (IOI09_mecho) Java 11
16 / 100
 839 ms 65536 KB 
/*
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT

1. Find shortest time it takes for the bees to reach every cell, and the shortest time it takes for Mecho to reach every cell (in minutes, take ceiling(steps it took for Mecho to get there (divided by) steps Mecho can take in a minute))
2. Binary search on the largest # of minutes that Mecho can eat honey for
*/
import java.util.*;
import java.io.*;

public class mecho{
  public static int n; 
  public static long s; 
  public static char[][] grid; //'T' = tree, 'G' = grass, 'M' = mecho, 'H' = beehive, 'D' = mecho's house
  //Neither bees or mecho can enter the tree cells
  //Mecho can travel s steps in 1 minute --> can reach a certain cell in ceil(steps it took to get to that cell/s) minutes, bees travel every minute 
  //Given that Mecho waited for x minutes, Mecho can visit a cell iff mecho[x][y] + x < bee[x][y] 
  public static long max = 9;//1000000000; 
  public static int denx; 
  public static int deny; 
  public static int mechox; 
  public static int mechoy; 

  public static long[][] bees; 
  public static long[][] mecho; 

  public static int[] xc = {0,0,1,-1};
  public static int[] yc = {1,-1,0,0};
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer details = new StringTokenizer(br.readLine());
    n = Integer.parseInt(details.nextToken());
    s = Long.parseLong(details.nextToken());
    grid = new char[n][n]; 

    bees = new long[n][n]; //bees[a][b] = min # of minutes it takes for a bee to reach cell a,b
    for(long[] row : bees) Arrays.fill(row, max);
    mecho = new long[n][n]; //mecho[a][b] = before division, min # of steps it takes for mecho to reach cell a,b, after division min # of minutes (ceiling)
    for(long[] row : mecho) Arrays.fill(row, max);
    ArrayDeque<State> bq = new ArrayDeque<State>(); //bee states
    ArrayDeque<State> mq = new ArrayDeque<State>(); //mecho states

    for(int a = 0; a < n; a++){
      String row = br.readLine(); 
      for(int b = 0; b < n; b++){
        char cur = row.charAt(b);
        grid[a][b] = cur; 

        if(cur == 'M'){
          mq.add(new State(a,b,0));
          mechox = a; 
          mechoy = b; 
          mecho[a][b] = 0; 
        }
        else if(cur == 'H'){
          bq.add(new State(a,b,0));
          bees[a][b] = 0; 
        }
        else if(cur == 'D'){
          denx = a; 
          deny = b; 
        }
      }
    }

    while(!bq.isEmpty()){
      State cur = bq.poll();         
      for(int a = 0; a < 4; a++){
        int xcoor = xc[a] + cur.x; 
        int ycoor = yc[a] + cur.y; 
        if(xcoor < 0 || ycoor < 0 || xcoor >= n || ycoor >= n || grid[xcoor][ycoor] == 'T' || grid[xcoor][ycoor] == 'D' || bees[xcoor][ycoor] != max) continue;
        bees[xcoor][ycoor] = cur.cost + 1; 
        bq.add(new State(xcoor, ycoor, cur.cost + 1));
      }
    }
    while(!mq.isEmpty()){
      State cur = mq.poll(); 
      for(int a = 0; a < 4; a++){
        int xcoor = xc[a] + cur.x; 
        int ycoor = yc[a] + cur.y; 
        if(xcoor < 0 || ycoor < 0 || xcoor >= n || ycoor >= n || grid[xcoor][ycoor] == 'T' || grid[xcoor][ycoor] == 'H' || mecho[xcoor][ycoor] != max) continue; 
        mecho[xcoor][ycoor] = (cur.cost + 1 + s-1)/s; 
        mq.add(new State(xcoor, ycoor, cur.cost + 1));
      }
    }

    //for(long[] row : mecho) System.out.println(Arrays.toString(row));
    //System.out.println("mecho ^ bees v");
    //for(long[] row : bees) System.out.println(Arrays.toString(row));

    long min = 0; 
    long max = n*n; //best case it takes the bees n*m time to reach Mecho/Mecho is able to evade the bees for n*m time
    while(min < max){
      long mid = (min + max + 1)/2; 
      //System.out.println(min + " " + mid + " " + max);
      if(valid(mid)) min = mid; 
      else max = mid - 1; //want to maximize answer
    }      
    if(min > 0 || valid(min)) System.out.println(min);
    else System.out.println(-1);
    br.close();
  }
  public static boolean valid(long x){
    long[][] distance = new long[n][n]; 
    for(long[] row : distance) Arrays.fill(row, max);
    distance[mechox][mechoy] = 0; 
    ArrayDeque<Point> ad = new ArrayDeque<Point>(); 
    ad.add(new Point(mechox, mechoy));
    while(!ad.isEmpty()){
      Point cur = ad.poll(); 
      for(int a = 0; a < 4; a++){
        int xcoor = xc[a] + cur.x; 
        int ycoor = yc[a] + cur.y; 
        if(xcoor < 0 || ycoor < 0 || xcoor >= n || ycoor >= n || distance[xcoor][ycoor] != max || mecho[xcoor][ycoor] == max || mecho[xcoor][ycoor] + x > bees[xcoor][ycoor]) continue; 
        if(mecho[xcoor][ycoor] + x < bees[xcoor][ycoor]){
          ad.add(new Point(xcoor, ycoor));
          distance[xcoor][ycoor] = distance[cur.x][cur.y] + 1;
        }
        else if(mecho[xcoor][ycoor] + x == bees[xcoor][ycoor] && (distance[cur.x][cur.y] + 1) % s != 0){
          ad.add(new Point(xcoor, ycoor));
          distance[xcoor][ycoor] = distance[cur.x][cur.y] + 1;
        }
      }
    }
    return distance[denx][deny] != max;
  }
}

class Point{
  int x; 
  int y; 
  public Point(int xc, int yc){
    x = xc; 
    y = yc; 
  }
  public String toString(){
    return x + " " + y; 
  }
}

class State{
  int x; 
  int y; 
  long cost; 
  public State(int xc, int yc, long c){
    x = xc;
    y = yc; 
    cost = c; 
  }
  public String toString(){
    return x + " " + y + " " + cost; 
  }
}

Subtask #1
16.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8512 KB Output is correct
2 Correct 58 ms 8220 KB Output is correct
3 Correct 60 ms 8296 KB Output is correct
4 Correct 66 ms 8152 KB Output is correct
5 Correct 58 ms 8376 KB Output is correct
6 Correct 60 ms 8548 KB Output is correct
7 Runtime error 353 ms 65536 KB Execution killed with signal 9
8 Correct 58 ms 8356 KB Output is correct
9 Incorrect 61 ms 8304 KB Output isn't correct
10 Incorrect 59 ms 8276 KB Output isn't correct
11 Incorrect 60 ms 8508 KB Output isn't correct
12 Incorrect 72 ms 8964 KB Output isn't correct
13 Incorrect 96 ms 10240 KB Output isn't correct
14 Correct 158 ms 13168 KB Output is correct
15 Incorrect 70 ms 8624 KB Output isn't correct
16 Incorrect 61 ms 8496 KB Output isn't correct
17 Incorrect 64 ms 8368 KB Output isn't correct
18 Incorrect 82 ms 10108 KB Output isn't correct
19 Incorrect 67 ms 8808 KB Output isn't correct
20 Incorrect 115 ms 13028 KB Output isn't correct
21 Incorrect 93 ms 11636 KB Output isn't correct
22 Incorrect 214 ms 36012 KB Output isn't correct
23 Incorrect 98 ms 11652 KB Output isn't correct
24 Runtime error 316 ms 65536 KB Execution killed with signal 9
25 Incorrect 98 ms 11804 KB Output isn't correct
26 Runtime error 318 ms 65536 KB Execution killed with signal 9
27 Incorrect 113 ms 12236 KB Output isn't correct
28 Runtime error 313 ms 65536 KB Execution killed with signal 9
29 Incorrect 120 ms 12544 KB Output isn't correct
30 Runtime error 317 ms 65536 KB Execution killed with signal 9
31 Incorrect 117 ms 12412 KB Output isn't correct
32 Runtime error 319 ms 65536 KB Execution killed with signal 9
33 Incorrect 318 ms 20904 KB Output isn't correct
34 Runtime error 384 ms 65536 KB Execution killed with signal 9
35 Incorrect 359 ms 21840 KB Output isn't correct
36 Incorrect 325 ms 23956 KB Output isn't correct
37 Runtime error 382 ms 65536 KB Execution killed with signal 9
38 Incorrect 366 ms 24544 KB Output isn't correct
39 Incorrect 350 ms 26904 KB Output isn't correct
40 Runtime error 381 ms 65536 KB Execution killed with signal 9
41 Incorrect 395 ms 27140 KB Output isn't correct
42 Incorrect 355 ms 30320 KB Output isn't correct
43 Runtime error 373 ms 65536 KB Execution killed with signal 9
44 Incorrect 432 ms 30996 KB Output isn't correct
45 Incorrect 354 ms 34008 KB Output isn't correct
46 Runtime error 324 ms 65536 KB Execution killed with signal 9
47 Incorrect 457 ms 35212 KB Output isn't correct
48 Incorrect 370 ms 37620 KB Output isn't correct
49 Runtime error 333 ms 65536 KB Execution killed with signal 9
50 Incorrect 546 ms 39052 KB Output isn't correct
51 Incorrect 386 ms 41824 KB Output isn't correct
52 Runtime error 357 ms 65536 KB Execution killed with signal 9
53 Incorrect 550 ms 41172 KB Output isn't correct
54 Incorrect 416 ms 46528 KB Output isn't correct
55 Runtime error 366 ms 65536 KB Execution killed with signal 9
56 Incorrect 618 ms 47432 KB Output isn't correct
57 Incorrect 446 ms 52268 KB Output isn't correct
58 Runtime error 341 ms 65536 KB Execution killed with signal 9
59 Incorrect 632 ms 50580 KB Output isn't correct
60 Incorrect 500 ms 56288 KB Output isn't correct
61 Runtime error 318 ms 65536 KB Execution killed with signal 9
62 Incorrect 678 ms 55848 KB Output isn't correct
63 Incorrect 644 ms 55356 KB Output isn't correct
64 Incorrect 839 ms 55788 KB Output isn't correct
65 Incorrect 814 ms 56552 KB Output isn't correct
66 Incorrect 756 ms 56084 KB Output isn't correct
67 Correct 652 ms 57048 KB Output is correct
68 Runtime error 393 ms 65536 KB Execution killed with signal 9
69 Runtime error 368 ms 65536 KB Execution killed with signal 9
70 Runtime error 362 ms 65536 KB Execution killed with signal 9
71 Incorrect 483 ms 51408 KB Output isn't correct
72 Runtime error 446 ms 65536 KB Execution killed with signal 9
73 Runtime error 336 ms 65536 KB Execution killed with signal 9
74 Incorrect 629 ms 55688 KB Output isn't correct
75 Runtime error 360 ms 65536 KB Execution killed with signal 9
76 Incorrect 522 ms 59896 KB Output isn't correct
77 Runtime error 350 ms 65536 KB Execution killed with signal 9
78 Runtime error 344 ms 65536 KB Execution killed with signal 9
79 Incorrect 655 ms 58540 KB Output isn't correct
80 Runtime error 350 ms 65536 KB Execution killed with signal 9
81 Runtime error 359 ms 65536 KB Execution killed with signal 9
82 Runtime error 357 ms 65536 KB Execution killed with signal 9
83 Runtime error 349 ms 65536 KB Execution killed with signal 9
84 Incorrect 638 ms 54608 KB Output isn't correct
85 Runtime error 355 ms 65536 KB Execution killed with signal 9
86 Runtime error 351 ms 65536 KB Execution killed with signal 9
87 Runtime error 360 ms 65536 KB Execution killed with signal 9
88 Runtime error 347 ms 65536 KB Execution killed with signal 9
89 Incorrect 659 ms 59604 KB Output isn't correct
90 Runtime error 355 ms 65536 KB Execution killed with signal 9
91 Runtime error 359 ms 65536 KB Execution killed with signal 9
92 Runtime error 339 ms 65536 KB Execution killed with signal 9