Submission #742712

#TimeUsernameProblemLanguageResultExecution timeMemory
742712airthsMecho (IOI09_mecho)C++17
39 / 100
516 ms16780 KiB
/* * * ^v^ * */ #include <iostream> #include <string> #include <cmath> #include <vector> #include <iomanip> #include <map> #include <numeric> #include <functional> #include <algorithm> #include <set> #include <queue> #include <climits> #include <cstdlib> #include <chrono> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; using namespace std; // #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> #define iamtefu ios_base::sync_with_stdio(false); cin.tie(0); #define ll long long int #define ld long double #define sc(a) scanf("%lld", &a); #define scv(a, n) vector<ll> a(n);fl(i,0,n){sc(a[i])} #define prl(a) fl(i,0,a.size()){printf("%lld ", a[i]);}printf("\n"); #define fl(i,a,n) for (ll i(a); i<n; i++) #define rfl(i,a,n) for (ll i(n-1); i>=a; i--) #define print(a) for (auto x:a){cout<<x<<" ";} cout<<"\n"; #define tt int tt; cin>>tt; for(;tt--;) ll gcd(ll a, ll b){ if (b==0){ return a; } return gcd(b, a%b); } ll pw(ll a, ll b, ll m){ ll res=1; a%=m; while (b){ if (b&1){ res=(res*a)%m; } a=(a*a)%m; b/=2; } return res; } void scn(){ ll n, s; cin>>n>>s; vector <string> c(n); vector <vector <ll>> a(n+1, vector <ll>(n+1, 1e9)); queue <vector <ll>> q; fl(i,0,n){ cin>>c[i]; fl(j,0,n){ if (c[i][j]=='H'){ q.push({i, j}); a[i][j]=0; } } } vector <ll> di={1, 1, 0, -1, -1, -1, 0, 1}; vector <ll> dj={0, 1, 1, 1, 0, -1, -1, -1}; while (!q.empty()){ auto j = q.front(); q.pop(); for (int d=0; d<8; d+=2){ ll i1 = j[0]+di[d], j1 = j[1]+dj[d]; if (i1>=0 && j1>=0 && i1<n && j1<n && a[i1][j1]==1e9 && (c[i1][j1]=='G' || c[i1][j1]=='M')){ q.push({i1, j1}); a[i1][j1]=a[j[0]][j[1]]+1; } } } vector <vector <ll>> dis(n+1, vector <ll>(n+1, 1e9)); vector <ll> hij; fl(i,0,n){ fl(j,0,n){ if (c[i][j]=='M'){ q.push({i, j}); dis[i][j]=0; hij={i, j}; } } } while (!q.empty()){ auto j = q.front(); q.pop(); for (int d=0; d<8; d+=2){ ll i1 = j[0]+di[d], j1 = j[1]+dj[d]; if (i1>=0 && j1>=0 && i1<n && j1<n && dis[i1][j1]==1e9 && (c[i1][j1]=='G' || c[i1][j1]=='D')){ dis[i1][j1]=dis[j[0]][j[1]]+1; q.push({i1, j1}); } } } for (auto &y:dis){ for (auto &x:y){ if (x!=1e9){ x=(x+s-1)/s; } } } if (a[hij[0]][hij[1]]==0){ cout<<"-1\n"; return; } // for (auto x:dis){ // print(x) // } // cout<<'\n'; // for (auto x:a){ // print(x) // } auto ist=[&](ll mid){ vector <vector <ll>> vis(n+1, vector <ll>(n+1)); queue <vector <ll>> q; q.push({hij[0], hij[1], s}); while (!q.empty()){ auto j = q.front(); q.pop(); if (c[j[0]][j[1]]=='D'){ return true; } if (j[2]==0 && dis[j[0]][j[1]]+mid>=a[j[0]][j[1]]){ // cout<<dis[j[0]][j[1]]<<" "<<mid<<" "<<a[j[0]][j[1]]<<" pl1\n"; continue; } else if (j[2] && dis[j[0]][j[1]]+mid-1>=a[j[0]][j[1]]){ continue; } // cout<<c[j[0]][j[1]]<<" pl\n"; for (int d=0; d<8; d+=2){ ll i1 = j[0]+di[d], j1 = j[1]+dj[d]; if (i1>=0 && i1<n && j1>=0 && j1<n && (c[i1][j1]=='D' || c[i1][j1]=='G') && vis[i1][j1]==0){ q.push({i1, j1, (j[2]==0?s-1:j[2]-1)}); vis[i1][j1]++; } } } return false; }; ll l = 0, r = n+1; // cout<<ist(3)<<" o\n"; while (l<=r){ // cout<<l<<" "<<r<<'\n'; ll mid = (l+r)/2; // cout<<mid<<" "<<ist(mid)<<" pl\n"; if (ist(mid)){ l = mid+1; } else { r = mid-1; } } if (ist(0)==0){ cout<<"-1\n"; return; } cout<<max(0ll,l-1)<<'\n'; // not necessarily distinct } int main(){ iamtefu; #if defined(airths) auto t1=chrono::high_resolution_clock::now(); freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else // #endif // tt { scn(); } #if defined(airths) auto t2=chrono::high_resolution_clock::now(); ld ti=chrono::duration_cast<chrono::nanoseconds>(t2-t1).count(); ti*=1e-6; cerr<<"Time: "<<setprecision(12)<<ti; cerr<<"ms\n"; #endif return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...