Submission #436854

#TimeUsernameProblemLanguageResultExecution timeMemory
436854adamjinweiMecho (IOI09_mecho)C++14
76 / 100
493 ms12476 KiB
#include <bits/stdc++.h> #define inf 100000000000000007 #define mod 1000000007 #define rnd() dist(rand_num) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #define int long long using namespace std; unsigned seed=std::chrono::system_clock::now().time_since_epoch().count(); mt19937 rand_num(seed); uniform_int_distribution<int> dist(0,inf); template <typename T> void read(T &x){ x=0;char ch=getchar();int fh=1; while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();} while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); x*=fh; } template <typename T> void write(T x) { if (x<0) x=-x,putchar('-'); if (x>9) write(x/10); putchar(x%10+'0'); } template <typename T> void writeln(T x) { write(x); puts(""); } const int dx[]={-1,0,1,0},dy[]={0,-1,0,1}; int n,s; char mp[805][1005]; int bee[805][805]; int bear[805][805]; bool check(int mid) { memset(bear,0x3f,sizeof(bear)); queue<pair<int,int>> q; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(mp[i][j]=='M') { if(mid>=bee[i][j]) return false; bear[i][j]=mid; q.push(make_pair(i,j)); } while(!q.empty()) { pair<int,int> p=q.front(); q.pop(); for(int d=0;d<4;++d) { int xx=p.first+dx[d],yy=p.second+dy[d]; if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&mp[xx][yy]!='T'&&mp[xx][yy]!='H'&&bear[p.first][p.second]+1<bee[xx][yy]&&bear[xx][yy]>bear[p.first][p.second]+1) { bear[xx][yy]=bear[p.first][p.second]+1; q.push(make_pair(xx,yy)); } } } for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(mp[i][j]=='D') { if(bear[i][j]<inf) return true; return false; } } signed main() { //freopen(".in","r",stdin); //freopen(".out","w",stdout); read(n);read(s); for(int i=1;i<=n;++i) scanf("%s",mp[i]+1); memset(bee,0x3f,sizeof(bee)); queue<pair<int,int>> q; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(mp[i][j]=='H') { bee[i][j]=0; q.push(make_pair(i,j)); } while(!q.empty()) { pair<int,int> p=q.front(); q.pop(); for(int d=0;d<4;++d) { int xx=p.first+dx[d],yy=p.second+dy[d]; if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&(mp[xx][yy]=='G'||mp[xx][yy]=='M')&&bee[xx][yy]>bee[p.first][p.second]+s) { bee[xx][yy]=bee[p.first][p.second]+s; q.push(make_pair(xx,yy)); } } } int l=0,r=5000000; while(l<r) { int mid=l+r+1>>1; if(check(mid)) l=mid; else r=mid-1; } if(check(l)) writeln(l/s); else puts("-1"); return 0; }

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:99:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |   int mid=l+r+1>>1;
      |           ~~~^~
mecho.cpp: In function 'bool check(long long int)':
mecho.cpp:35:23: warning: control reaches end of non-void function [-Wreturn-type]
   35 |  queue<pair<int,int>> q;
      |                       ^
mecho.cpp: In function 'int main()':
mecho.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%s",mp[i]+1);
      |   ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...