oj.uz

Submission #442064

# Submission time Handle Problem Language Result Execution time Memory
442064 2021-07-07T01:15:02 Z dawangk Mecho (IOI09_mecho) C++14
15 / 100
 1000 ms 22816 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 = 8e3+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}};
bool v[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 x, int y, int t, int used){
    //for(int i= 0;i<n;i++){
    //    for(int j = 0;j<n;j++){
    //        cout<<v[i][j]<<" ";
    //    }cout<<ell;
    //}cout<<t<<" "<<used<<ell;

    int newt = (used+1==k)?t+1:t;
    int newused = (used+1)%k;
    if(x==ex&&y==ey)return true;
    for(int i = 0;i<4;i++){
        int newx = x+dir[i].f, newy = y+dir[i].s;
        //cout<<newx<<" "<<newy<<endl;
        if(vv(newx)&&vv(newy)&&(grid[newx][newy]=='G'||grid[newx][newy]=='D')&&newt<dist[newx][newy]&&!v[newx][newy]){
            v[newx][newy] = true;
            if(dfs(newx, newy, newt, newused))return true;
            v[newx][newy] = false;
        }
    }
    return false;
}

bool dfss(int t){
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            v[i][j] = false;
        }
    }
    v[sx][sy] = true;
    return dfs(sx, sy, t-1, k-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 = dist[sx][sy];
    //dfss(3);

    while(lo<hi){
        //cout<<lo<<" "<<hi<<endl;
        int mid = (lo+hi+1)/2;
        if(dfss(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
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Execution timed out 1100 ms 14672 KB Time limit exceeded
8 Incorrect 1 ms 460 KB Output isn't correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Incorrect 1 ms 972 KB Output isn't correct
13 Execution timed out 1085 ms 844 KB Time limit exceeded
14 Execution timed out 1099 ms 972 KB Time limit exceeded
15 Incorrect 1 ms 460 KB Output isn't correct
16 Correct 1 ms 452 KB Output is correct
17 Incorrect 1 ms 604 KB Output isn't correct
18 Correct 1 ms 588 KB Output is correct
19 Incorrect 1 ms 588 KB Output isn't correct
20 Correct 1 ms 588 KB Output is correct
21 Incorrect 1 ms 716 KB Output isn't correct
22 Correct 1 ms 716 KB Output is correct
23 Incorrect 1 ms 844 KB Output isn't correct
24 Correct 1 ms 844 KB Output is correct
25 Incorrect 1 ms 972 KB Output isn't correct
26 Correct 1 ms 972 KB Output is correct
27 Incorrect 1 ms 1100 KB Output isn't correct
28 Correct 1 ms 1100 KB Output is correct
29 Incorrect 1 ms 1100 KB Output isn't correct
30 Correct 1 ms 1228 KB Output is correct
31 Incorrect 1 ms 1228 KB Output isn't correct
32 Correct 1 ms 1228 KB Output is correct
33 Incorrect 7 ms 5440 KB Output isn't correct
34 Correct 8 ms 6476 KB Output is correct
35 Execution timed out 1090 ms 6988 KB Time limit exceeded
36 Incorrect 9 ms 6248 KB Output isn't correct
37 Correct 12 ms 7752 KB Output is correct
38 Execution timed out 1097 ms 8396 KB Time limit exceeded
39 Incorrect 11 ms 7116 KB Output isn't correct
40 Correct 12 ms 9164 KB Output is correct
41 Execution timed out 1088 ms 9844 KB Time limit exceeded
42 Incorrect 12 ms 8132 KB Output isn't correct
43 Correct 14 ms 10432 KB Output is correct
44 Execution timed out 1084 ms 11340 KB Time limit exceeded
45 Incorrect 15 ms 9036 KB Output isn't correct
46 Correct 18 ms 11980 KB Output is correct
47 Execution timed out 1086 ms 13080 KB Time limit exceeded
48 Incorrect 17 ms 10092 KB Output isn't correct
49 Correct 19 ms 13560 KB Output is correct
50 Execution timed out 1095 ms 14844 KB Time limit exceeded
51 Incorrect 19 ms 11120 KB Output isn't correct
52 Correct 23 ms 15204 KB Output is correct
53 Execution timed out 1094 ms 16628 KB Time limit exceeded
54 Incorrect 25 ms 12172 KB Output isn't correct
55 Correct 26 ms 16904 KB Output is correct
56 Execution timed out 1088 ms 18576 KB Time limit exceeded
57 Incorrect 30 ms 13276 KB Output isn't correct
58 Correct 29 ms 18656 KB Output is correct
59 Execution timed out 1085 ms 20676 KB Time limit exceeded
60 Incorrect 30 ms 14384 KB Output isn't correct
61 Correct 37 ms 20568 KB Output is correct
62 Execution timed out 1089 ms 22816 KB Time limit exceeded
63 Correct 89 ms 14532 KB Output is correct
64 Correct 94 ms 14508 KB Output is correct
65 Correct 89 ms 14620 KB Output is correct
66 Incorrect 94 ms 14620 KB Output isn't correct
67 Incorrect 117 ms 14512 KB Output isn't correct
68 Correct 55 ms 14540 KB Output is correct
69 Correct 44 ms 14528 KB Output is correct
70 Correct 45 ms 14552 KB Output is correct
71 Correct 50 ms 14596 KB Output is correct
72 Incorrect 42 ms 14392 KB Output isn't correct
73 Execution timed out 1093 ms 15008 KB Time limit exceeded
74 Execution timed out 1056 ms 16076 KB Time limit exceeded
75 Execution timed out 1092 ms 14784 KB Time limit exceeded
76 Execution timed out 1093 ms 14648 KB Time limit exceeded
77 Execution timed out 1088 ms 14912 KB Time limit exceeded
78 Execution timed out 1077 ms 14748 KB Time limit exceeded
79 Execution timed out 1088 ms 14840 KB Time limit exceeded
80 Execution timed out 1096 ms 14660 KB Time limit exceeded
81 Execution timed out 1084 ms 14568 KB Time limit exceeded
82 Execution timed out 1084 ms 14888 KB Time limit exceeded
83 Execution timed out 1084 ms 14660 KB Time limit exceeded
84 Execution timed out 1091 ms 14696 KB Time limit exceeded
85 Execution timed out 1091 ms 14680 KB Time limit exceeded
86 Execution timed out 1088 ms 14588 KB Time limit exceeded
87 Execution timed out 1083 ms 14580 KB Time limit exceeded
88 Execution timed out 1088 ms 14532 KB Time limit exceeded
89 Execution timed out 1090 ms 14656 KB Time limit exceeded
90 Execution timed out 1060 ms 14660 KB Time limit exceeded
91 Execution timed out 1086 ms 14656 KB Time limit exceeded
92 Execution timed out 1078 ms 14528 KB Time limit exceeded