| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 914715 |
2024-01-22T15:17:02 Z |
_saketks_07 |
Mecho (IOI09_mecho) |
C++17 |
|
127 ms |
64108 KB |
#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
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
504 KB |
Output isn't correct |
| 5 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
127 ms |
64108 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 11 |
| 13 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 14 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 15 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 16 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 21 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 22 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 23 |
Runtime error |
1 ms |
708 KB |
Execution killed with signal 11 |
| 24 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 11 |
| 25 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 11 |
| 26 |
Runtime error |
2 ms |
964 KB |
Execution killed with signal 11 |
| 27 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 28 |
Correct |
1 ms |
604 KB |
Output is correct |
| 29 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 30 |
Correct |
1 ms |
604 KB |
Output is correct |
| 31 |
Incorrect |
1 ms |
684 KB |
Output isn't correct |
| 32 |
Correct |
1 ms |
600 KB |
Output is correct |
| 33 |
Runtime error |
9 ms |
9164 KB |
Execution killed with signal 11 |
| 34 |
Runtime error |
8 ms |
9056 KB |
Execution killed with signal 11 |
| 35 |
Runtime error |
11 ms |
9252 KB |
Execution killed with signal 11 |
| 36 |
Runtime error |
15 ms |
11488 KB |
Execution killed with signal 11 |
| 37 |
Runtime error |
15 ms |
11540 KB |
Execution killed with signal 11 |
| 38 |
Runtime error |
19 ms |
11728 KB |
Execution killed with signal 11 |
| 39 |
Runtime error |
14 ms |
14456 KB |
Execution killed with signal 11 |
| 40 |
Runtime error |
14 ms |
14452 KB |
Execution killed with signal 11 |
| 41 |
Runtime error |
24 ms |
20556 KB |
Execution killed with signal 11 |
| 42 |
Runtime error |
17 ms |
17524 KB |
Execution killed with signal 11 |
| 43 |
Runtime error |
17 ms |
17548 KB |
Execution killed with signal 11 |
| 44 |
Runtime error |
33 ms |
17700 KB |
Execution killed with signal 11 |
| 45 |
Runtime error |
21 ms |
21128 KB |
Execution killed with signal 11 |
| 46 |
Runtime error |
29 ms |
21016 KB |
Execution killed with signal 11 |
| 47 |
Runtime error |
39 ms |
30544 KB |
Execution killed with signal 11 |
| 48 |
Runtime error |
32 ms |
24988 KB |
Execution killed with signal 11 |
| 49 |
Runtime error |
25 ms |
25048 KB |
Execution killed with signal 11 |
| 50 |
Runtime error |
32 ms |
25052 KB |
Execution killed with signal 11 |
| 51 |
Runtime error |
30 ms |
29220 KB |
Execution killed with signal 11 |
| 52 |
Runtime error |
29 ms |
29140 KB |
Execution killed with signal 11 |
| 53 |
Runtime error |
39 ms |
29180 KB |
Execution killed with signal 11 |
| 54 |
Runtime error |
32 ms |
33756 KB |
Execution killed with signal 11 |
| 55 |
Runtime error |
33 ms |
33580 KB |
Execution killed with signal 11 |
| 56 |
Runtime error |
45 ms |
33756 KB |
Execution killed with signal 11 |
| 57 |
Runtime error |
38 ms |
38516 KB |
Execution killed with signal 11 |
| 58 |
Runtime error |
37 ms |
38400 KB |
Execution killed with signal 11 |
| 59 |
Runtime error |
57 ms |
38512 KB |
Execution killed with signal 11 |
| 60 |
Runtime error |
43 ms |
43656 KB |
Execution killed with signal 11 |
| 61 |
Runtime error |
42 ms |
43704 KB |
Execution killed with signal 11 |
| 62 |
Runtime error |
64 ms |
43700 KB |
Execution killed with signal 11 |
| 63 |
Runtime error |
68 ms |
43704 KB |
Execution killed with signal 11 |
| 64 |
Runtime error |
58 ms |
43716 KB |
Execution killed with signal 11 |
| 65 |
Runtime error |
60 ms |
43848 KB |
Execution killed with signal 11 |
| 66 |
Runtime error |
60 ms |
43784 KB |
Execution killed with signal 11 |
| 67 |
Runtime error |
57 ms |
43716 KB |
Execution killed with signal 11 |
| 68 |
Runtime error |
79 ms |
63948 KB |
Execution killed with signal 6 |
| 69 |
Runtime error |
78 ms |
63900 KB |
Execution killed with signal 6 |
| 70 |
Runtime error |
77 ms |
63948 KB |
Execution killed with signal 6 |
| 71 |
Runtime error |
77 ms |
63740 KB |
Execution killed with signal 6 |
| 72 |
Runtime error |
83 ms |
63828 KB |
Execution killed with signal 6 |
| 73 |
Incorrect |
92 ms |
32508 KB |
Output isn't correct |
| 74 |
Incorrect |
87 ms |
32336 KB |
Output isn't correct |
| 75 |
Incorrect |
93 ms |
32332 KB |
Output isn't correct |
| 76 |
Incorrect |
87 ms |
32344 KB |
Output isn't correct |
| 77 |
Incorrect |
88 ms |
32496 KB |
Output isn't correct |
| 78 |
Incorrect |
75 ms |
32344 KB |
Output isn't correct |
| 79 |
Incorrect |
75 ms |
32348 KB |
Output isn't correct |
| 80 |
Correct |
79 ms |
32356 KB |
Output is correct |
| 81 |
Correct |
75 ms |
32208 KB |
Output is correct |
| 82 |
Incorrect |
79 ms |
32444 KB |
Output isn't correct |
| 83 |
Correct |
91 ms |
32200 KB |
Output is correct |
| 84 |
Correct |
93 ms |
32348 KB |
Output is correct |
| 85 |
Correct |
89 ms |
32344 KB |
Output is correct |
| 86 |
Incorrect |
101 ms |
32592 KB |
Output isn't correct |
| 87 |
Correct |
95 ms |
32340 KB |
Output is correct |
| 88 |
Correct |
91 ms |
32080 KB |
Output is correct |
| 89 |
Correct |
98 ms |
32256 KB |
Output is correct |
| 90 |
Correct |
89 ms |
32184 KB |
Output is correct |
| 91 |
Correct |
99 ms |
32264 KB |
Output is correct |
| 92 |
Correct |
96 ms |
32092 KB |
Output is correct |
