Submission #914715

#TimeUsernameProblemLanguageResultExecution timeMemory
914715_saketks_07Mecho (IOI09_mecho)C++17
8 / 100
127 ms64108 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> /// order_of_key return number of elements less than x. /// find_by_order return index. const int N = 3*1e5 + 10; const int M = 1e9+7; #define ll long long int #define ld long double #define rep(i, n) for (ll i = 0; i < n; i++) #define ff first #define ss second #define rep1(i, n) for (ll i = 1; i < n; i++) #define repr(i, n) for (ll i = n - 1; i >= 0; i--) #define pb push_back #define vi vector<int> #define vll vector<long long> #define vpll vector<pair<ll, ll>> #define vvll vector<vector<ll>> #define vvpll vector<vector<pll>> #define pll pair<ll, ll> #define endl "\n" const ll INF = 2e18+1; ll binmult(int a, int b) { ll ans = 0; while (b > 0) { if (b & 1) ans = (ans + a) % M; a = (a + a) % M; b >>= 1; } return ans; } ll binpow(int a, int b) { ll ans = 1; while (b > 0) { if (b & 1) ans = binmult(ans, a); a = binmult(a, a); b >>= 1; } return ans; } ll bs_sqrt(ll x) { ll left = 0, right = 2000000123; while (right > left) { ll mid = (left + right) / 2; if (mid * mid > x) right = mid; else left = mid + 1; } return left - 1; } ll inverse(ll x,ll M){ ll y=binmult(x,M-2); return y; } // ll nCr(ll n, ll r) // { // return ((fac(n)*inverse(fac(n-r)))%M*inverse(fac(r)))%M; // } //---------------------------------------------------------------------- // DSU // vll par(N+1,0),sz(N+1,0); // void make(int x){ // par[x]=x;sz[x]=1; // } // int find(int x){ // if(x==par[x]) return x; // return par[x]=find(par[x]); // } // void Union(int b,int a){ // a=find(a),b=find(b); // // if(a!=b) // { // if(sz[a]<sz[b]) swap(a,b); // sz[a]+=sz[b]; // par[b]=a; // } // } //-------------------------------------------------------------------- // Dynamic Range Minimum Segment Tree // vll a(N), seg(4*N); // void build(int ind, int low, int high){ // if(low==high) {seg[ind]=a[low]; return ;} // ll mid=(high+low)/2; // build(2*ind+1, low, mid); // build(2*ind+2, mid+1,high); // seg[ind]=min(seg[2*ind+1], seg[2*ind+2]); // } // void update(ll ind, ll low,ll high, ll i, ll val){ // if(low==high ){ // if(low==i) // seg[ind]=val; // return ; // } // if(i<low || i>high) return ; // ll mid=(high+low)/2; // update(2*ind+1,low, mid, i, val); // update(2*ind+2,mid+1, high, i, val); // seg[ind]=min(seg[2*ind+1], seg[2*ind+2]); // return ; // } // ll query(ll ind, ll low,ll high, ll l, ll r){ // if(l<=low && high<=r) return seg[ind]; // if(high< l || low>r) return INT_MAX; // ll mid=(high+low)/2; // return min(query(2*ind+1, low, mid, l, r), query(2*ind+2, mid+1, high, l, r)); // } //----------------------------------------------------------------------- // vll vis(5000,0); // void gen(ll ver, ll i, ll l, ll r,vvll &g, vll &b, vll &d){ // ll n=d.size(); // vpll v; // vis[ver]=1; // for(int it=i+1;it<n;it++) // { // if(vis[b[it]]) continue; // g[ver].pb(b[it]); // ll ind=find(d.begin(), d.end(),b[it])-d.begin(); // v.pb({ind,it}); // if(ind==l) break; // } // sort(v.begin(),v.end()); // rep(j,v.size()-1){ // if(v[j].ff+1==v[j+1].ff) continue; // gen(b[v[j].ss],v[j].ss, v[j].ff+1, v[j+1].ff-1,g,b,d); // } // pll x=v.back(); // gen(b[x.ss], x.ss, x.ff+1, n-1,g,b,d); // } bool isvalid(ll i, ll j, vector<vector<char>> &v){ if(i>=0 && i<v.size() && j>=0 && j<v[0].size() && v[i][j]!='T') return true; return false; } void bfs(queue<pll> &q, vector<vector<char>> &v, vvll &vis, vvll &dis, vvpll &p){ // dis[1]=0; vll dx={0,0,1,-1}; vll dy={1,-1,0,0}; while(!q.empty()){ auto cur=q.front(); q.pop(); if(vis[cur.ff][cur.ss]) continue; vis[cur.ff][cur.ss]=1; for(int i=0;i<4;i++){ ll x=cur.ff+dx[i], y= cur.ss+dy[i]; if(isvalid(x,y,v) && dis[x][y] > dis[cur.ff][cur.ss]+1){ dis[x][y] = dis[cur.ff][cur.ss]+1; p[x][y]={cur.ff, cur.ss}; q.push({x,y}); } } } } // void dfs(ll a,ll b, ll c, ll d, vector<vector<char>> &g, vll &vis, vll &dis){ // vis[a][b]=1; // st.push({a,b}); // for(auto it:g[i]){ // if(!vis[it]) { // dis[it]=dis[i]+1; // dfs(it,g,vis,dis); // } // } // vis[i]=0; // } void solve(){ ll n,s;cin>>n>>s; vector<vector<char>> v(n, vector<char>(n)); rep(i,n){ rep(j,n) { char c;cin>>c; v[i][j]=c; } } queue<pll> q; vvll vis(n,vll(n,0)), vis2(n,vll(n,0)); vvll dis(n,vll(n,INF)), dis2(n,vll(n,INF)); ll a,b,c,d; rep(i,n){ rep(j,n){ if(v[i][j]=='H') {q.push({i,j}); dis[i][j]=0;} if(v[i][j]=='M') {a=i,b=j, dis2[i][j]=0;} if(v[i][j]=='D') {c=i, d=j;} } } // cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl; vvpll p(n,vpll(n)); bfs(q,v,vis,dis,p); while(!q.empty()) q.pop(); q.push({a,b}); p.clear(); bfs(q,v,vis2,dis2,p); // rep(i,n){ // rep(j,n){ // // cout<<p[i][j].ff<<"-"<<p[i][j].ss<<" "; // } // // cout<<endl; // } vpll vec; ll x=c, y=d; while(make_pair(x,y)!=make_pair(a,b)){ // cout<<x<<" "<<y<<"\n"; vec.pb({x,y}); pll ch=p[x][y]; x=ch.ff,y=ch.ss; } ll ans=INF, len=dis2[c][d]; rep(i,vec.size()){ ll x=vec[i].ff, y=vec[i].ss; ans=min(ans, dis[x][y]- (dis2[x][y]+s-1)/s); } if(ans==INF) cout<<-1<<endl; else cout<<ans<<endl; } int main() { // freopen("atlarge.in", "r", stdin); // freopen("atlarge.out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t=1; // cin >> t; ll tt = 1; ll p=1; while (t--) { solve(); tt++; } return 0; } /* to get the maxsum, and minsum of a array from start but processing from end:- suppose s is the array, sul - suffix_minsum, sur - suffix_maxsum for (int i = n - 1; i >= 0; --i){ int d = s[i]; sul.push_back(min(0, sul.back() + d)); sur.push_back(max(0, sur.back() + d)); } */

Compilation message (stderr)

mecho.cpp: In function 'bool isvalid(long long int, long long int, std::vector<std::vector<char> >&)':
mecho.cpp:153:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     if(i>=0 && i<v.size() && j>=0 && j<v[0].size() && v[i][j]!='T') return true;
      |                ~^~~~~~~~~
mecho.cpp:153:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     if(i>=0 && i<v.size() && j>=0 && j<v[0].size() && v[i][j]!='T') return true;
      |                                      ~^~~~~~~~~~~~
mecho.cpp: In function 'void solve()':
mecho.cpp:17:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define rep(i, n) for (ll i = 0; i < n; i++)
......
  236 |     rep(i,vec.size()){
      |         ~~~~~~~~~~~~                
mecho.cpp:236:5: note: in expansion of macro 'rep'
  236 |     rep(i,vec.size()){
      |     ^~~
mecho.cpp:235:17: warning: unused variable 'len' [-Wunused-variable]
  235 |     ll ans=INF, len=dis2[c][d];
      |                 ^~~
mecho.cpp: In function 'int main()':
mecho.cpp:257:12: warning: unused variable 'p' [-Wunused-variable]
  257 |         ll p=1;
      |            ^
mecho.cpp: In function 'void solve()':
mecho.cpp:232:22: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
  232 |         pll ch=p[x][y];
      |                      ^
mecho.cpp:232:19: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
  232 |         pll ch=p[x][y];
      |                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...