Submission #442068

#TimeUsernameProblemLanguageResultExecution timeMemory
442068dawangkMecho (IOI09_mecho)C++14
37 / 100
1098 ms16572 KiB
#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}}; 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; //cout<<x<<" "<<y<<" "<<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, 0); } 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(!dfss(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(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 (stderr)

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;
      |                                                             ~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...