oj.uz

Submission #567910

# Submission time Handle Problem Language Result Execution time Memory
567910 2022-05-24T10:44:06 Z Quan2003 Mecho (IOI09_mecho) C++17
12 / 100
 315 ms 16220 KB 
#include <bits/stdc++.h>
#include <iostream>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
const int sz=1005;
int n,s;
int d1[sz][sz];
int d0[sz][sz];
bool vis1[sz][sz];
bool vis0[sz][sz];
vector<pair<int,int>>hiv;
int px,py;
int dx,dy;
ll step[sz][sz];
int movex[4]={0,0,1,-1};
int movey[4]={-1,1,0,0};
char c[sz][sz];
void bfs(vector<pair<int,int>>&a,int d[sz][sz],bool visited[sz][sz]){
    queue<pair<int,int>>q;
    for (auto i:a){
        q.push(i);
        visited[i.first][i.second]=1;
    }
    while (!q.empty()){
        int x1=q.front().first;
        int y1=q.front().second;
        q.pop();
        for (int i=0;i<4;i++){
            int x2=x1+movex[i];
            int y2=y1+movey[i];
            if (x2<0 or x2>=n) continue;
            if (y2<0 or y2>=n) continue;
            if (c[x2][y2]=='D' or c[x2][y2]=='T' or visited[x2][y2]) continue;
            visited[x2][y2]=1;
            d[x2][y2]=d[x1][y1]+1;
            q.push({x2,y2}); 
        }
    } 
}
bool bsearch(int k){
    for (int i=0;i<n;i++){
       for(int j=0;j<n;j++){
           vis1[i][j]=0;
           d1[i][j]=0;
           step[i][j]=INT_MAX;
       }
    }
    queue<pair<int,int>>q;
    q.push({px,py});
    step[px][py]=k;
    while (!q.empty()){
        int sx=q.front().first;
        int sy=q.front().second;
        q.pop();
        for (int i=0;i<4;i++){
            int tx=sx+movex[i];
            int ty=sy+movey[i];
            if (tx<0 or tx>=n) continue;
            if (ty<0 or ty>=n) continue;
            if (c[tx][ty]=='H' or c[tx][ty]=='T' or vis1[tx][ty]) continue;
            d1[tx][ty]=d1[sx][sy]+1;
            int moves=k+d1[tx][ty]/s;
            if (moves>=d0[tx][ty]) continue;
            step[tx][ty]=moves+1;
            vis1[tx][ty]=1;
            q.push({tx,ty});
        }
    } for (int i=0;i<4;i++){
         int tx=dx+movex[i];
         int ty=dy+movey[i];
         if (tx<0 or tx>=n or ty<0 or ty>=n or c[tx][ty]=='T' or c[tx][ty]=='H') continue;
         if (step[tx][ty]<=d0[tx][ty]) return 1;
    } return 0;
}
int main(){
    cin>>n>>s;
    for (int i=0;i<n;i++){
        for(int j=0;j<n;j++){
             cin>>c[i][j];
             if (c[i][j]=='D'){
                 dx=i;dy=j;
             }
             if (c[i][j]=='M'){
                 px=i;py=j;
             } if (c[i][j]=='H'){
                 hiv.push_back({i,j});
             }
        }
    } 
      bfs(hiv,d0,vis0);
      int low=0;int high=1e9;
      while (high>low){
          int mid=low+(high-low+1)/2;
          if (bsearch(mid)) low=mid;
          else high=mid-1;
      } 
        if (!bsearch(low)) cout <<-1;
        else cout <<bsearch(1);
         
}

Subtask #1
12.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Incorrect 175 ms 16000 KB Output isn't correct
8 Correct 1 ms 468 KB Output is correct
9 Incorrect 1 ms 448 KB Output isn't correct
10 Incorrect 1 ms 468 KB Output isn't correct
11 Incorrect 1 ms 468 KB Output isn't correct
12 Incorrect 2 ms 1236 KB Output isn't correct
13 Incorrect 2 ms 1080 KB Output isn't correct
14 Correct 2 ms 1236 KB Output is correct
15 Incorrect 1 ms 596 KB Output isn't correct
16 Incorrect 1 ms 596 KB Output isn't correct
17 Incorrect 1 ms 596 KB Output isn't correct
18 Incorrect 1 ms 596 KB Output isn't correct
19 Incorrect 1 ms 724 KB Output isn't correct
20 Incorrect 1 ms 724 KB Output isn't correct
21 Incorrect 1 ms 852 KB Output isn't correct
22 Incorrect 1 ms 852 KB Output isn't correct
23 Incorrect 1 ms 980 KB Output isn't correct
24 Incorrect 1 ms 980 KB Output isn't correct
25 Incorrect 1 ms 1236 KB Output isn't correct
26 Incorrect 1 ms 1160 KB Output isn't correct
27 Incorrect 1 ms 1236 KB Output isn't correct
28 Incorrect 2 ms 1236 KB Output isn't correct
29 Incorrect 2 ms 1364 KB Output isn't correct
30 Incorrect 2 ms 1344 KB Output isn't correct
31 Incorrect 2 ms 1364 KB Output isn't correct
32 Incorrect 2 ms 1364 KB Output isn't correct
33 Incorrect 20 ms 6588 KB Output isn't correct
34 Incorrect 17 ms 6508 KB Output isn't correct
35 Incorrect 44 ms 6572 KB Output isn't correct
36 Incorrect 19 ms 7636 KB Output isn't correct
37 Incorrect 19 ms 7636 KB Output isn't correct
38 Incorrect 51 ms 7652 KB Output isn't correct
39 Incorrect 25 ms 8748 KB Output isn't correct
40 Incorrect 25 ms 8788 KB Output isn't correct
41 Incorrect 63 ms 8772 KB Output isn't correct
42 Incorrect 32 ms 9896 KB Output isn't correct
43 Incorrect 32 ms 9832 KB Output isn't correct
44 Incorrect 73 ms 9908 KB Output isn't correct
45 Incorrect 34 ms 10884 KB Output isn't correct
46 Incorrect 38 ms 10836 KB Output isn't correct
47 Incorrect 102 ms 10848 KB Output isn't correct
48 Incorrect 45 ms 11856 KB Output isn't correct
49 Incorrect 50 ms 11852 KB Output isn't correct
50 Incorrect 111 ms 11888 KB Output isn't correct
51 Incorrect 56 ms 12864 KB Output isn't correct
52 Incorrect 60 ms 12976 KB Output isn't correct
53 Incorrect 128 ms 12828 KB Output isn't correct
54 Incorrect 76 ms 13772 KB Output isn't correct
55 Incorrect 81 ms 13748 KB Output isn't correct
56 Incorrect 161 ms 13876 KB Output isn't correct
57 Incorrect 82 ms 14880 KB Output isn't correct
58 Incorrect 95 ms 14964 KB Output isn't correct
59 Incorrect 228 ms 14880 KB Output isn't correct
60 Incorrect 101 ms 15848 KB Output isn't correct
61 Incorrect 115 ms 15880 KB Output isn't correct
62 Incorrect 240 ms 15772 KB Output isn't correct
63 Correct 202 ms 15892 KB Output is correct
64 Incorrect 315 ms 15896 KB Output isn't correct
65 Incorrect 292 ms 15892 KB Output isn't correct
66 Incorrect 248 ms 15868 KB Output isn't correct
67 Correct 210 ms 15852 KB Output is correct
68 Correct 118 ms 15916 KB Output is correct
69 Incorrect 148 ms 15852 KB Output isn't correct
70 Incorrect 139 ms 15912 KB Output isn't correct
71 Incorrect 113 ms 15836 KB Output isn't correct
72 Incorrect 107 ms 15916 KB Output isn't correct
73 Correct 142 ms 16060 KB Output is correct
74 Incorrect 166 ms 16184 KB Output isn't correct
75 Incorrect 138 ms 16076 KB Output isn't correct
76 Incorrect 138 ms 16220 KB Output isn't correct
77 Incorrect 154 ms 16204 KB Output isn't correct
78 Correct 155 ms 16144 KB Output is correct
79 Incorrect 150 ms 16024 KB Output isn't correct
80 Incorrect 143 ms 16144 KB Output isn't correct
81 Incorrect 147 ms 16208 KB Output isn't correct
82 Incorrect 149 ms 16144 KB Output isn't correct
83 Correct 167 ms 16096 KB Output is correct
84 Incorrect 157 ms 16080 KB Output isn't correct
85 Incorrect 151 ms 16080 KB Output isn't correct
86 Incorrect 159 ms 16100 KB Output isn't correct
87 Incorrect 184 ms 16100 KB Output isn't correct
88 Correct 170 ms 15924 KB Output is correct
89 Incorrect 202 ms 16044 KB Output isn't correct
90 Incorrect 194 ms 16028 KB Output isn't correct
91 Incorrect 174 ms 15952 KB Output isn't correct
92 Incorrect 177 ms 16052 KB Output isn't correct