Submission #442178

#TimeUsernameProblemLanguageResultExecution timeMemory
442178HaidaraMecho (IOI09_mecho)C++17
20 / 100
391 ms12084 KiB
/* * * * * * * * * *\ * Author: Haidara * * LANG: C++17 * * PROB: * \* * * * * * * * * */ #include<bits/stdc++.h> #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define int long long #define rep(i,x,n) for(int i=x;i<(n);i++) #define FOR(i,n) rep(i,0,n) #define per(i,x,n) for(int i=x;i>(n);i--) #define ROF(i,x) for(int i=x;i>=0;i--) #define v(i) vector< i > #define p(i,j) pair< i , j > #define pii pair<int,int> #define m(i,j) map< i , j > #define um(i,j) unordered_map< i , j > #define pq(i) priority_queue< i > #define ff first #define all(x) x.begin(),x.end() #define ss second #define pp push_back using namespace std; void SIO(string name="") { if(name!="") { freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout); } } const int inf=1LL<<60LL; const int mod=1e9+7; const int maxn=808; int n,foot; pii Mecho,House; char a[maxn][maxn]; bool vis[maxn][maxn]; queue<pii>q; v(v(int)) dist; int dx[] {-1,1,0,0}; int dy[] {0,0,-1,1}; bool valid(int x,int y) { return x>=0&&y>=0&&x<n&&y<n&&a[x][y]=='G'; } bool nvalid(int x,int y) { return x>=0&&y>=0&&x<n&&y<n; } bool check(int Time) { v(v(int))newdist; newdist=dist; FOR(i,maxn) FOR(j,maxn) { vis[i][j]=0; if(a[i][j]=='T'||a[i][j]=='H'||a[i][j]=='M') vis[i][j]=1; } queue<p(pii,int)>nq; nq.push({Mecho,foot}); newdist[Mecho.ff][Mecho.ss]=Time; while(nq.size()) { pii f=nq.front().ff; int lft=nq.front().ss; nq.pop(); FOR(i,4) { int x=f.ff+dx[i],y=f.ss+dy[i]; if(nvalid(x,y)&&(a[x][y]=='G'||a[x][y]=='D')) { if(!vis[x][y]) { if(lft) { if(newdist[x][y]>newdist[f.ff][f.ss]) { newdist[x][y]=newdist[f.ff][f.ss]; nq.push({{x,y},lft-1}); vis[x][y]=1; } } else { if(newdist[x][y]>newdist[f.ff][f.ss]+1) { newdist[x][y]=newdist[f.ff][f.ss]; nq.push({{x,y},foot}); vis[x][y]=1; } } } } } } return newdist[House.ff][House.ss]!=inf; } void solve() { while(q.size()) { pii f=q.front(); q.pop(); FOR(i,4) { int x=f.ff+dx[i],y=f.ss+dy[i]; if(valid(x,y)) { if(!vis[x][y]) { vis[x][y]=1; q.push({x,y}); dist[x][y]=dist[f.ff][f.ss]+1; } else if(dist[x][y]>dist[f.ff][f.ss]+1) { dist[x][y]=dist[f.ff][f.ss]+1; q.push({x,y}); } } } } } signed main() { SIO(""); cin>>n>>foot; dist.resize(maxn); FOR(i,maxn) dist[i].resize(maxn); FOR(i,n) FOR(j,n) { cin>>a[i][j]; dist[i][j]=inf; if(a[i][j]=='M') Mecho= {i,j}; else if(a[i][j]=='H') q.push({i,j}),vis[i][j]=1,dist[i][j]=0; else if(a[i][j]=='T') vis[i][j]=1; else if(a[i][j]=='D') House={i,j}; } solve(); int l=1,r=800*800,ans=-1; while(l<=r) { int mid=l+(r-l)/2; if(check(mid)) ans=max(ans,mid-1),l=mid+1; else r=mid-1; } cout<<ans; }

Compilation message (stderr)

mecho.cpp: In function 'void SIO(std::string)':
mecho.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...