oj.uz

Submission #131458

# Submission time Handle Problem Language Result Execution time Memory
131458 2019-07-17T07:27:49 Z dragonslayerit Mecho (IOI09_mecho) C++14
0 / 100
 659 ms 26768 KB 
#include <cstdio>
#include <queue>
#include <tuple>

const int INF=1e9+7;

const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};

char grid[1005][1005];
int danger[1005][1005];

int dist[1005][1005];
int N,S;

void dump(int vs[1005][1005]){
  for(int x=0;x<N;x++){
    for(int y=0;y<N;y++){
      if(vs[x][y]!=INF){
	printf("%d",vs[x][y]);
      }else{
	printf("-");
      }
    }
    printf("\n");
  }
  printf("\n");
}

bool check(int start){
  printf("check(%d)\n",start);
  for(int x=0;x<N;x++){
    for(int y=0;y<N;y++){
      dist[x][y]=INF;
    }
  }
  std::queue<std::pair<int,int> > mecho;
  for(int x=0;x<N;x++){
    for(int y=0;y<N;y++){
      if(grid[x][y]=='M'){
	dist[x][y]=0;
	mecho.push({x,y});
      }
    }
  }
  while(!mecho.empty()){
    int x,y;
    std::tie(x,y)=mecho.front();
    mecho.pop();
    if(dist[x][y]/S+start>=danger[x][y]) continue;
    if(grid[x][y]=='D'){
      dump(dist);
      return true;
    }
    for(int d=0;d<4;d++){
      int x2=x+dx[d],y2=y+dy[d];
      if((grid[x2][y2]=='G'||grid[x2][y2]=='D')&&dist[x2][y2]==INF){
	dist[x2][y2]=dist[x][y]+1;
	mecho.push({x2,y2});
      }
    }
  }
  dump(dist);
  return false;
}

int main(){
  scanf("%d %d",&N,&S);
  for(int x=0;x<N;x++){
    scanf("%s",grid[x]);
  }
  for(int x=0;x<N;x++){
    for(int y=0;y<N;y++){
      danger[x][y]=INF;
    }
  }
  std::queue<std::pair<int,int> > bees;
  for(int x=0;x<N;x++){
    for(int y=0;y<N;y++){
      if(grid[x][y]=='H'){
	danger[x][y]=0;
	bees.push({x,y});
      }
    }
  }
  while(!bees.empty()){
    int x,y;
    std::tie(x,y)=bees.front();
    bees.pop();
    for(int d=0;d<4;d++){
      int x2=x+dx[d],y2=y+dy[d];
      if((grid[x2][y2]=='G'||grid[x2][y2]=='M')&&danger[x2][y2]==INF){
	danger[x2][y2]=danger[x][y]+1;
	bees.push({x2,y2});
      }
    }
  }
  dump(danger);
  int low=-1,high=N*2;
  while(high-low>1){
    int mid=(low+high)/2;
    if(check(mid)){
      low=mid;
    }else{
      high=mid;
    }
  }
  printf("%d\n",low);
  return 0;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&N,&S);
   ~~~~~^~~~~~~~~~~~~~~
mecho.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",grid[x]);
     ~~~~~^~~~~~~~~~~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Incorrect 564 ms 21780 KB Output isn't correct
8 Incorrect 2 ms 376 KB Output isn't correct
9 Incorrect 2 ms 504 KB Output isn't correct
10 Incorrect 2 ms 376 KB Output isn't correct
11 Incorrect 2 ms 504 KB Output isn't correct
12 Incorrect 4 ms 888 KB Output isn't correct
13 Incorrect 3 ms 760 KB Output isn't correct
14 Incorrect 9 ms 1020 KB Output isn't correct
15 Incorrect 2 ms 504 KB Output isn't correct
16 Incorrect 2 ms 508 KB Output isn't correct
17 Incorrect 2 ms 504 KB Output isn't correct
18 Incorrect 2 ms 508 KB Output isn't correct
19 Incorrect 2 ms 632 KB Output isn't correct
20 Incorrect 2 ms 632 KB Output isn't correct
21 Incorrect 3 ms 632 KB Output isn't correct
22 Incorrect 3 ms 632 KB Output isn't correct
23 Incorrect 3 ms 760 KB Output isn't correct
24 Incorrect 3 ms 760 KB Output isn't correct
25 Incorrect 4 ms 888 KB Output isn't correct
26 Incorrect 4 ms 888 KB Output isn't correct
27 Incorrect 5 ms 1016 KB Output isn't correct
28 Incorrect 4 ms 1016 KB Output isn't correct
29 Incorrect 5 ms 1016 KB Output isn't correct
30 Incorrect 5 ms 1016 KB Output isn't correct
31 Incorrect 5 ms 1016 KB Output isn't correct
32 Incorrect 5 ms 1144 KB Output isn't correct
33 Incorrect 64 ms 5212 KB Output isn't correct
34 Incorrect 65 ms 5160 KB Output isn't correct
35 Incorrect 108 ms 6168 KB Output isn't correct
36 Incorrect 81 ms 6136 KB Output isn't correct
37 Incorrect 87 ms 6136 KB Output isn't correct
38 Incorrect 154 ms 7844 KB Output isn't correct
39 Incorrect 112 ms 7160 KB Output isn't correct
40 Incorrect 102 ms 7140 KB Output isn't correct
41 Incorrect 191 ms 9440 KB Output isn't correct
42 Incorrect 130 ms 8312 KB Output isn't correct
43 Incorrect 128 ms 8284 KB Output isn't correct
44 Incorrect 240 ms 11368 KB Output isn't correct
45 Incorrect 164 ms 9812 KB Output isn't correct
46 Incorrect 164 ms 9804 KB Output isn't correct
47 Incorrect 288 ms 13456 KB Output isn't correct
48 Incorrect 198 ms 11096 KB Output isn't correct
49 Incorrect 194 ms 11148 KB Output isn't correct
50 Incorrect 338 ms 15648 KB Output isn't correct
51 Incorrect 226 ms 12540 KB Output isn't correct
52 Incorrect 227 ms 12456 KB Output isn't correct
53 Incorrect 405 ms 18072 KB Output isn't correct
54 Incorrect 260 ms 14072 KB Output isn't correct
55 Incorrect 263 ms 14072 KB Output isn't correct
56 Incorrect 483 ms 20536 KB Output isn't correct
57 Incorrect 299 ms 15636 KB Output isn't correct
58 Incorrect 303 ms 15608 KB Output isn't correct
59 Incorrect 544 ms 23020 KB Output isn't correct
60 Incorrect 346 ms 17256 KB Output isn't correct
61 Incorrect 348 ms 17192 KB Output isn't correct
62 Incorrect 658 ms 26768 KB Output isn't correct
63 Incorrect 538 ms 21540 KB Output isn't correct
64 Incorrect 659 ms 24964 KB Output isn't correct
65 Incorrect 657 ms 24924 KB Output isn't correct
66 Incorrect 536 ms 21752 KB Output isn't correct
67 Incorrect 596 ms 21540 KB Output isn't correct
68 Incorrect 423 ms 17400 KB Output isn't correct
69 Incorrect 405 ms 17244 KB Output isn't correct
70 Incorrect 379 ms 16912 KB Output isn't correct
71 Incorrect 384 ms 16840 KB Output isn't correct
72 Incorrect 359 ms 16316 KB Output isn't correct
73 Incorrect 398 ms 17784 KB Output isn't correct
74 Incorrect 473 ms 19064 KB Output isn't correct
75 Incorrect 446 ms 18904 KB Output isn't correct
76 Incorrect 474 ms 19704 KB Output isn't correct
77 Incorrect 447 ms 18964 KB Output isn't correct
78 Incorrect 484 ms 19832 KB Output isn't correct
79 Incorrect 448 ms 19192 KB Output isn't correct
80 Incorrect 438 ms 18580 KB Output isn't correct
81 Incorrect 503 ms 20372 KB Output isn't correct
82 Incorrect 463 ms 19448 KB Output isn't correct
83 Incorrect 536 ms 21112 KB Output isn't correct
84 Incorrect 514 ms 20640 KB Output isn't correct
85 Incorrect 514 ms 20644 KB Output isn't correct
86 Incorrect 550 ms 20972 KB Output isn't correct
87 Incorrect 516 ms 20788 KB Output isn't correct
88 Incorrect 554 ms 21240 KB Output isn't correct
89 Incorrect 549 ms 21596 KB Output isn't correct
90 Incorrect 577 ms 21788 KB Output isn't correct
91 Incorrect 548 ms 21728 KB Output isn't correct
92 Incorrect 496 ms 20216 KB Output isn't correct