oj.uz

Submission #928831

# Submission time Handle Problem Language Result Execution time Memory
928831 2024-02-17T06:26:48 Z absolutePi Mecho (IOI09_mecho) C++17
5 / 100
 443 ms 6940 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 800;
int n,s;
int mx[]={1,-1,0,0},my[]={0,0,1,-1};
vector<vector<char>> grid(N,vector<char>(N));


bool valid_sit(int x,int y){
    return (x>=0&&y>=0&&x<n&&y<n&&(grid[x][y]=='G'||grid[x][y]=='M'));
}

bool mecho_reached(int m,int b){
    return (m/s)<b;
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    cin >> n >> s;
    vector<pair<int,int>> bees;
    pair<int,int> mecho,home;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin >> grid[i][j];
            if(grid[i][j]=='H'){
                bees.push_back({i,j});
            }
            if(grid[i][j]=='M'){
                mecho = {i,j};
            }
            if(grid[i][j]=='D'){
                home = {i,j};
            }
        }
    }
    int l=0,r=n*n;
    while(l<=r){
        vector<vector<bool>> visb(n,vector<bool>(n)),vism(n,vector<bool>(n));
        vector<vector<int>> distb(n,vector<int>(n)),distm(n,vector<int>(n));    
        queue<pair<int,int>> q;
        int eating_time=l+(r-l)/2;
        for(auto i : bees){
            q.push(i);
            visb[i.first][i.second]=true;
        }
        while(!q.empty()){
            int x,y;
            tie(x,y)=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int newx=x+mx[i];
                int newy=y+my[i];
                if(valid_sit(newx,newy)&&!visb[newx][newy]){
                    distb[newx][newy]=distb[x][y]+1;
                    q.push({newx,newy});
                    visb[newx][newy]=true;
                }
            }
        }
        q.push(mecho);
        vism[mecho.first][mecho.second]=true;
        if(distb[mecho.first][mecho.second]<=eating_time){q.pop();}
        while(!q.empty()){
            int x,y;
            tie(x,y)=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int newx=x+mx[i];
                int newy=y+my[i];
                if(valid_sit(newx,newy)&&!vism[newx][newy]&&(mecho_reached(distm[x][y]+1,distb[newx][newy]-eating_time))){
                    distm[newx][newy]=distm[x][y]+1;
                    q.push({newx,newy});
                    vism[newx][newy]=true;
                }
            }
        }
        bool reached=false;
        for(int i=0;i<4;i++){
            int newx=home.first+mx[i];
            int newy=home.second+my[i];
            if(valid_sit(newx,newy)&&(mecho_reached(distm[newx][newy],distb[newx][newy]-eating_time))){
                reached=true;
            }
        }
        if(reached){
            l=eating_time+1;
        }
        else{
            r=eating_time-1;
        }
    }
    cout << l-1 << '\n';
}

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Incorrect 1 ms 860 KB Output isn't correct
3 Incorrect 1 ms 860 KB Output isn't correct
4 Incorrect 1 ms 860 KB Output isn't correct
5 Incorrect 1 ms 860 KB Output isn't correct
6 Incorrect 1 ms 860 KB Output isn't correct
7 Incorrect 443 ms 6468 KB Output isn't correct
8 Incorrect 1 ms 856 KB Output isn't correct
9 Incorrect 1 ms 860 KB Output isn't correct
10 Incorrect 1 ms 860 KB Output isn't correct
11 Incorrect 1 ms 860 KB Output isn't correct
12 Correct 2 ms 1116 KB Output is correct
13 Incorrect 2 ms 1116 KB Output isn't correct
14 Incorrect 2 ms 1116 KB Output isn't correct
15 Incorrect 1 ms 860 KB Output isn't correct
16 Incorrect 1 ms 860 KB Output isn't correct
17 Incorrect 1 ms 860 KB Output isn't correct
18 Incorrect 1 ms 860 KB Output isn't correct
19 Incorrect 1 ms 860 KB Output isn't correct
20 Incorrect 1 ms 860 KB Output isn't correct
21 Incorrect 1 ms 1116 KB Output isn't correct
22 Incorrect 1 ms 1116 KB Output isn't correct
23 Incorrect 1 ms 1116 KB Output isn't correct
24 Incorrect 1 ms 1112 KB Output isn't correct
25 Incorrect 2 ms 1116 KB Output isn't correct
26 Incorrect 2 ms 1116 KB Output isn't correct
27 Incorrect 2 ms 1116 KB Output isn't correct
28 Incorrect 2 ms 1116 KB Output isn't correct
29 Incorrect 2 ms 1116 KB Output isn't correct
30 Incorrect 2 ms 1116 KB Output isn't correct
31 Incorrect 2 ms 1116 KB Output isn't correct
32 Incorrect 2 ms 1116 KB Output isn't correct
33 Incorrect 34 ms 2156 KB Output isn't correct
34 Incorrect 33 ms 2148 KB Output isn't correct
35 Incorrect 60 ms 2140 KB Output isn't correct
36 Incorrect 47 ms 2428 KB Output isn't correct
37 Incorrect 43 ms 2460 KB Output isn't correct
38 Incorrect 88 ms 2440 KB Output isn't correct
39 Incorrect 60 ms 2804 KB Output isn't correct
40 Incorrect 55 ms 2812 KB Output isn't correct
41 Incorrect 120 ms 2652 KB Output isn't correct
42 Incorrect 74 ms 3204 KB Output isn't correct
43 Incorrect 79 ms 3208 KB Output isn't correct
44 Incorrect 137 ms 3164 KB Output isn't correct
45 Incorrect 94 ms 3600 KB Output isn't correct
46 Incorrect 82 ms 3632 KB Output isn't correct
47 Incorrect 179 ms 3608 KB Output isn't correct
48 Incorrect 117 ms 4152 KB Output isn't correct
49 Incorrect 102 ms 4116 KB Output isn't correct
50 Incorrect 204 ms 4180 KB Output isn't correct
51 Incorrect 131 ms 4600 KB Output isn't correct
52 Incorrect 119 ms 4612 KB Output isn't correct
53 Incorrect 242 ms 4444 KB Output isn't correct
54 Incorrect 151 ms 5168 KB Output isn't correct
55 Incorrect 139 ms 5428 KB Output isn't correct
56 Incorrect 269 ms 5164 KB Output isn't correct
57 Incorrect 172 ms 5760 KB Output isn't correct
58 Incorrect 157 ms 5768 KB Output isn't correct
59 Incorrect 321 ms 5744 KB Output isn't correct
60 Incorrect 206 ms 6408 KB Output isn't correct
61 Incorrect 181 ms 6364 KB Output isn't correct
62 Incorrect 402 ms 6392 KB Output isn't correct
63 Incorrect 350 ms 6232 KB Output isn't correct
64 Incorrect 359 ms 6392 KB Output isn't correct
65 Incorrect 352 ms 6232 KB Output isn't correct
66 Incorrect 350 ms 6704 KB Output isn't correct
67 Incorrect 337 ms 6388 KB Output isn't correct
68 Incorrect 376 ms 6416 KB Output isn't correct
69 Incorrect 373 ms 6228 KB Output isn't correct
70 Incorrect 371 ms 6480 KB Output isn't correct
71 Incorrect 368 ms 6224 KB Output isn't correct
72 Incorrect 378 ms 6412 KB Output isn't correct
73 Incorrect 371 ms 6696 KB Output isn't correct
74 Incorrect 410 ms 6904 KB Output isn't correct
75 Incorrect 396 ms 6684 KB Output isn't correct
76 Incorrect 400 ms 6940 KB Output isn't correct
77 Incorrect 422 ms 6688 KB Output isn't correct
78 Incorrect 405 ms 6620 KB Output isn't correct
79 Incorrect 402 ms 6836 KB Output isn't correct
80 Incorrect 383 ms 6488 KB Output isn't correct
81 Incorrect 401 ms 6740 KB Output isn't correct
82 Incorrect 390 ms 6656 KB Output isn't correct
83 Incorrect 418 ms 6736 KB Output isn't correct
84 Incorrect 417 ms 6488 KB Output isn't correct
85 Incorrect 421 ms 6860 KB Output isn't correct
86 Incorrect 406 ms 6452 KB Output isn't correct
87 Incorrect 425 ms 6740 KB Output isn't correct
88 Incorrect 417 ms 6552 KB Output isn't correct
89 Incorrect 428 ms 6488 KB Output isn't correct
90 Incorrect 440 ms 6492 KB Output isn't correct
91 Incorrect 421 ms 6564 KB Output isn't correct
92 Incorrect 425 ms 6556 KB Output isn't correct