| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 914715 | _saketks_07 | Mecho (IOI09_mecho) | C++17 | 127 ms | 64108 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||