oj.uz

Submission #442472

# Submission time Handle Problem Language Result Execution time Memory
442472 2021-07-07T20:09:24 Z dawangk Mecho (IOI09_mecho) C++14
64 / 100
 229 ms 8900 KB 
#include <bits/stdc++.h>
using namespace std;
#define inputJunk ios_base::sync_with_stdio(0); cin.tie(0);
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug cout<<"HERE"<<endl;
#define ell "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<pi, int> trip;
typedef pair<pll, ll> tripll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<trip> vtrip;

const int INF = 1e9+1212;
const ll P = 9973, M = 1e9+9;
const int MM = 8e2+5; int mod = 1e9+7;//998244353

int n, k, sx, sy, ex, ey, dist[MM][MM]; char grid[MM][MM];
queue<pi> q; pi dir[4] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
pi step[MM][MM];

bool vv(int a){
    return a>=0&&a<n;
}

bool valid(int x, int y){
    return vv(x)&&vv(y)&&(grid[x][y]=='G'||grid[x][y]=='M')&dist[x][y]==-1;
}

bool dfs(int t){
    queue<pi> q;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            step[i][j] = {-1, 0};
        }
    }
    step[sx][sy] = {t, 0};
    q.push({sx, sy});
    while(!q.empty()){
        int x = q.front().f, y = q.front().s; q.pop();
        for(int i = 0;i<4;i++){
            int newx = x+dir[i].f, newy = y+dir[i].s;
            int newt = (step[x][y].s+1==k)?step[x][y].f+1:step[x][y].f;
            int newused = (step[x][y].s+1)%k;
            //cout<<newx<<" "<<newy<<endl;
            if(vv(newx)&&vv(newy)&&(grid[newx][newy]=='G'||grid[newx][newy]=='D')&&newt<dist[newx][newy]&&step[newx][newy].f==-1){

                step[newx][newy] = {newt, newused};
                q.push({newx, newy});
            }
        }
    }
    //cout<<t<<ell;
    /*
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cout<<"("<<step[i][j].f<<" "<<step[i][j].s<<")"<<" ";
        }cout<<ell;
    }*/
    return step[ex][ey].f!=-1;
}

int main(){
    inputJunk
    cin>>n>>k;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cin>>grid[i][j];
            dist[i][j] = -1;
            if(grid[i][j]=='M'){sx = i; sy = j;}
            else if(grid[i][j]=='D'){ex = i;ey = j;}
            else if(grid[i][j]=='H'){q.push({i, j}); dist[i][j] = 0;}
        }
    }

    while(!q.empty()){
        int curx = q.front().f, cury = q.front().s;q.pop();
        //cout<<curx<<" "<<cury<<" "<<endl;
        for(int i = 0;i<4;i++){
            int newx = curx+dir[i].f, newy = cury+dir[i].s;
            if(valid(newx, newy)){
                dist[newx][newy] = dist[curx][cury]+1;
                q.push({newx, newy});
            }
        }
    }
/*
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cout<<dist[i][j]<<" ";
        }cout<<ell;
    }*/
    dist[ex][ey] = INF;
    int lo = 0, hi = 100000;
    if(!dfs(0)){
        cout<<-1<<endl;
        return 0;
    }
    //cout<<"BOB"<<dfss(2)<<ell;

    while(lo<hi){
        //cout<<lo<<" "<<hi<<endl;
        int mid = (lo+hi+1)/2;
        if(dfs(mid)){
            lo = mid;
        }else{
            hi = mid-1;
        }
    }
    cout<<lo<<endl;

}
/*CUSTOM TEST CASE 1
*/

/*CUSTOM TEST CASE 2
*/

/*CUSTOM TEST CASE 3
*/

/*Comments of Shame
- floating error (use integer division instead)
- cin vs getline
- upperbound and lowerbound returns iteratorsf
- use long long when number is big enough
- for dp invalid cases needs to be skipped
- some base cases won't work (review cow poetry)
- always check bounds, some TLE are due to incorrect bounds!
- dont mess up return types
= RESET ARRAYS!!!!!!!!!!
- USE UR BRAIN
- INF setting problems
*/
/*
    freopen("time.in","r", stdin);
    freopen("time.out","w", stdout);
*/

Compilation message

mecho.cpp: In function 'bool valid(int, int)':
mecho.cpp:36:71: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   36 |     return vv(x)&&vv(y)&&(grid[x][y]=='G'||grid[x][y]=='M')&dist[x][y]==-1;
      |                                                             ~~~~~~~~~~^~~~

Subtask #1
64.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 166 ms 8576 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Incorrect 1 ms 716 KB Output isn't correct
13 Incorrect 1 ms 716 KB Output isn't correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 588 KB Output is correct
22 Correct 1 ms 588 KB Output is correct
23 Correct 1 ms 716 KB Output is correct
24 Correct 1 ms 716 KB Output is correct
25 Correct 1 ms 716 KB Output is correct
26 Correct 1 ms 716 KB Output is correct
27 Correct 1 ms 844 KB Output is correct
28 Correct 1 ms 844 KB Output is correct
29 Correct 1 ms 844 KB Output is correct
30 Correct 1 ms 844 KB Output is correct
31 Correct 1 ms 844 KB Output is correct
32 Correct 1 ms 844 KB Output is correct
33 Correct 9 ms 3876 KB Output is correct
34 Correct 10 ms 3900 KB Output is correct
35 Correct 35 ms 3888 KB Output is correct
36 Correct 12 ms 4428 KB Output is correct
37 Correct 14 ms 4300 KB Output is correct
38 Correct 46 ms 4340 KB Output is correct
39 Incorrect 16 ms 4932 KB Output isn't correct
40 Correct 18 ms 4932 KB Output is correct
41 Correct 60 ms 4916 KB Output is correct
42 Incorrect 30 ms 5324 KB Output isn't correct
43 Correct 25 ms 5324 KB Output is correct
44 Correct 79 ms 5436 KB Output is correct
45 Incorrect 34 ms 5948 KB Output isn't correct
46 Correct 27 ms 5956 KB Output is correct
47 Correct 91 ms 5964 KB Output is correct
48 Incorrect 44 ms 6444 KB Output isn't correct
49 Correct 29 ms 6348 KB Output is correct
50 Correct 109 ms 6400 KB Output is correct
51 Incorrect 56 ms 6860 KB Output isn't correct
52 Incorrect 40 ms 6860 KB Output isn't correct
53 Correct 135 ms 6988 KB Output is correct
54 Incorrect 67 ms 7428 KB Output isn't correct
55 Incorrect 59 ms 7484 KB Output isn't correct
56 Correct 148 ms 7476 KB Output is correct
57 Incorrect 84 ms 7880 KB Output isn't correct
58 Incorrect 99 ms 7980 KB Output isn't correct
59 Correct 188 ms 7992 KB Output is correct
60 Incorrect 99 ms 8500 KB Output isn't correct
61 Incorrect 128 ms 8504 KB Output isn't correct
62 Correct 229 ms 8516 KB Output is correct
63 Correct 139 ms 8500 KB Output is correct
64 Correct 225 ms 8592 KB Output is correct
65 Correct 202 ms 8472 KB Output is correct
66 Correct 187 ms 8388 KB Output is correct
67 Correct 44 ms 8388 KB Output is correct
68 Correct 70 ms 8492 KB Output is correct
69 Correct 71 ms 8516 KB Output is correct
70 Correct 62 ms 8492 KB Output is correct
71 Correct 63 ms 8616 KB Output is correct
72 Incorrect 54 ms 8524 KB Output isn't correct
73 Incorrect 75 ms 8772 KB Output isn't correct
74 Correct 111 ms 8832 KB Output is correct
75 Correct 114 ms 8900 KB Output is correct
76 Correct 110 ms 8900 KB Output is correct
77 Correct 106 ms 8776 KB Output is correct
78 Correct 48 ms 8644 KB Output is correct
79 Correct 119 ms 8756 KB Output is correct
80 Correct 121 ms 8832 KB Output is correct
81 Correct 131 ms 8748 KB Output is correct
82 Correct 100 ms 8704 KB Output is correct
83 Correct 129 ms 8716 KB Output is correct
84 Correct 144 ms 8668 KB Output is correct
85 Correct 134 ms 8712 KB Output is correct
86 Correct 170 ms 8660 KB Output is correct
87 Correct 136 ms 8676 KB Output is correct
88 Correct 162 ms 8620 KB Output is correct
89 Correct 154 ms 8604 KB Output is correct
90 Correct 146 ms 8644 KB Output is correct
91 Correct 152 ms 8656 KB Output is correct
92 Correct 147 ms 8664 KB Output is correct