#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#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>
#define iiordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
//Bit Functions
#define gcd __gcd
#define lsb __builtin_ffs
#define ldz __builtin_clz
#define tlz __builtin_ctz
#define stc __builtin_popcount
#define prtb(n) cout << bitset<20>(n) << "\n";
//Debugging
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define what_is(x) cerr << #x << " is " << x << endl;
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << endl;
err(++it, args...);
}
//STL Declarations
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<long long int>
#define vvl vector<vl>
#define vb vector<bool>
#define pii pair<int,int>
#define fr first
#define sc second
#define u_s unordered_set
#define ump unordered_map
#define ins insert
#define p_q(x) priority_queue<x>
//STL Functions
#define mt make_tuple
#define eb emplace_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define muq make_unique
#define all(x) x.begin(),x.end()
#define rot(vec,k) rotate(vec.begin(), vec.begin() + k, vec.end());
#define bs(vec,key) binary_search(all(vec), key)
#define parti(vec,p) partition_point(all(vec), p) - vec.begin()
#define srt(cnt) sort(all(cnt))
#define lb(cnt,x) lower_bound(all(cnt),x)
#define ub(cnt,x) upper_bound(all(cnt),x)
#define mxm(cnt) *max_element(all(cnt))
#define mnm(cnt) *min_element(all(cnt))
#define mxmptr(cnt) max_element(all(cnt))
#define mnmptr(cnt) min_element(all(cnt))
#define rev(cnt) reverse(all(cnt))
#define accum(cnt) accumulate(all(cnt),0)
#define look(cnt) for(auto c:cnt) cout<<c<<" "; cout<<"\n";
#define pre(x,cont) find(all(cont),x)!=cont.end()
#define pb push_back
//Input Functions
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << t<<" "; return os << endl; }
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << v.first << " " << v.second ; }
typedef long long int ll;
ll mod = 10000000007;
//Generalised Sum Function
int sum() { return 0; }
template<typename T, typename... Args>
T sum(T a, Args... args) { return a + sum(args...); }
vector<int> seive(int N){
vector<bool> visited(N+1,false);
vi pr;
for(int i=2;i<=N;i++){
if(!visited[i]){
int j = i;
pr.pb(j);
while(j<=N){visited[j] = true;j+=i;}}}
return pr;
}
ll ceil(ll a,ll b){
if(b<0)a=-a,b=-b;
if(a>=0)return (a+b-1)/b;
return a/b;
}
long long bpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
ll inverse(ll a,ll m=mod)
{
return bpow(a,m-2,m);
}
vvl matmul(const vvl &a,const vvl &b,ll M=mod)
{
int n=a.size(),m=a[0].size(),l=b[0].size();
assert(m==b.size());
vvl c(n,vl(l,0));
rep(i,0,n)
rep(j,0,l)
rep(k,0,m)
{
c[i][j]=(c[i][j]+a[i][k]*b[k][j])%M;
}
return c;
}
vvl matpow(vvl a,ll p,ll M=mod)
{
assert(a.size()==a[0].size());
int n=a.size();
vvl res(n,vl(n,0));
rep(i,0,n) res[i][i]=1;
while(p>0)
{
if(p&1) res=matmul(res,a,M);
a=matmul(a,a,M);
p>>=1;
}
return res;
}
const ll COMBINATION_SIZE = 300005;
const ll MOD = 1e9+7;
struct Combination {
long long fac[COMBINATION_SIZE], inv[COMBINATION_SIZE];
bool built = 0;
void build(){
assert(MOD >= COMBINATION_SIZE);
fac[0] = 1;
for(int i = 1; i < COMBINATION_SIZE; i++) {
fac[i] = fac[i - 1] * i % MOD;
}
inv[COMBINATION_SIZE - 1] = inverse(fac[COMBINATION_SIZE - 1], MOD);
for(int i = COMBINATION_SIZE - 2; i >= 0; i--) {
inv[i] = inv[i + 1] * (i + 1) % MOD;
}
}
long long C(int x, int y){
if(y < 0 || y > x) {
return 0;
}
if(!built) {
built = 1;
build();
}
return fac[x] * inv[y] % MOD * inv[x-y] % MOD;
}
} comb;
void setIO(string s) { // the argument is the filename without the extension
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
int main(){ _
int n,s;cin >> n >> s;
vector<string> vec(n);
rep(i,0,n)
cin >> vec[i];
auto valid = [&](int x,int y){
if(x<0 || y<0 || x>=n || y>=n)
return false;
return true;
};
vector<pii> dirs = {{+1,0},{-1,0},{0,+1},{0,-1}};
pii start;pii end;
queue<pii> q;
vector<vi> d(n,vi(n,-1));
rep(i,0,n){
rep(j,0,n){
if(vec[i][j] == 'H'){
q.push({i,j});
d[i][j] = 0;
}
else if(vec[i][j] == 'M'){
start = {i,j};
vec[i][j] = 'G';
}
else if(vec[i][j] == 'D'){
end = {i,j};
}
}
}
// The bee action is finished!
while(!q.empty()){
auto p = q.front();q.pop();
int x = p.fr;int y = p.sc;
int dd = d[x][y];
for(auto c:dirs){
int X = x+c.fr;
int Y = y+c.sc;
if(valid(X,Y) && (d[X][Y] == -1) && vec[X][Y]=='G'){
q.push({X,Y});
d[X][Y] = dd+s;
}
}
}
d[end.fr][end.sc] = INT_MAX;
auto check = [&](int start_time){
if(d[start.fr][start.sc] <= start_time*s)
return false;
queue<pii> q2;
vector<vi> d2(n,vi(n,-1));
q2.push(start);
d2[start.fr][start.sc] = start_time*s;
while(!q2.empty()){
auto p = q2.front();
if(p == end)
return true;
q2.pop();
int x = p.fr;
int y = p.sc;
int dd = d2[x][y];
int chk = dd + 1;
for(auto c:dirs){
int X = x + c.fr;
int Y = y + c.sc;
if(valid(X,Y) && d2[X][Y] == -1 && vec[X][Y] != 'T' && chk < d[X][Y]){
d2[X][Y] = chk;
q2.push({X,Y});
}
}
}
return d2[end.fr][end.sc]!=-1;
};
if(!check(0)){
cout << "-1\n";
}
else{
int r = n*n*2;
int l = 0;
while(r-l>1){
int mid = (l+r)/2;
if(check(mid)){
l = mid;
}
else{
r = mid;
}
}
cout << l << "\n";
}
return 0;
}
Compilation message
In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
from mecho.cpp:4:
mecho.cpp: In function 'std::vector<std::vector<long long int> > matmul(const std::vector<std::vector<long long int> >&, const std::vector<std::vector<long long int> >&, ll)':
mecho.cpp:111:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | assert(m==b.size());
| ~^~~~~~~~~~
mecho.cpp: In function 'void setIO(std::string)':
mecho.cpp:166:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
166 | freopen((s+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:167:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
167 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
113 ms |
6104 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
0 ms |
332 KB |
Output is correct |
22 |
Correct |
0 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
5 ms |
1436 KB |
Output is correct |
34 |
Correct |
5 ms |
1452 KB |
Output is correct |
35 |
Correct |
26 ms |
1440 KB |
Output is correct |
36 |
Correct |
7 ms |
1740 KB |
Output is correct |
37 |
Correct |
6 ms |
1740 KB |
Output is correct |
38 |
Correct |
36 ms |
1764 KB |
Output is correct |
39 |
Correct |
8 ms |
2144 KB |
Output is correct |
40 |
Correct |
8 ms |
2148 KB |
Output is correct |
41 |
Correct |
41 ms |
2184 KB |
Output is correct |
42 |
Correct |
11 ms |
2588 KB |
Output is correct |
43 |
Correct |
11 ms |
2592 KB |
Output is correct |
44 |
Correct |
50 ms |
2596 KB |
Output is correct |
45 |
Correct |
14 ms |
3096 KB |
Output is correct |
46 |
Correct |
14 ms |
3096 KB |
Output is correct |
47 |
Correct |
64 ms |
3060 KB |
Output is correct |
48 |
Correct |
17 ms |
3572 KB |
Output is correct |
49 |
Correct |
16 ms |
3576 KB |
Output is correct |
50 |
Correct |
87 ms |
3604 KB |
Output is correct |
51 |
Correct |
20 ms |
4188 KB |
Output is correct |
52 |
Correct |
19 ms |
4148 KB |
Output is correct |
53 |
Correct |
101 ms |
4148 KB |
Output is correct |
54 |
Correct |
21 ms |
4780 KB |
Output is correct |
55 |
Correct |
18 ms |
4772 KB |
Output is correct |
56 |
Correct |
115 ms |
4740 KB |
Output is correct |
57 |
Correct |
23 ms |
5436 KB |
Output is correct |
58 |
Correct |
23 ms |
5412 KB |
Output is correct |
59 |
Correct |
131 ms |
5384 KB |
Output is correct |
60 |
Correct |
24 ms |
6092 KB |
Output is correct |
61 |
Correct |
30 ms |
6112 KB |
Output is correct |
62 |
Correct |
155 ms |
6116 KB |
Output is correct |
63 |
Correct |
135 ms |
6168 KB |
Output is correct |
64 |
Correct |
255 ms |
6128 KB |
Output is correct |
65 |
Correct |
187 ms |
6076 KB |
Output is correct |
66 |
Correct |
167 ms |
6092 KB |
Output is correct |
67 |
Correct |
46 ms |
5980 KB |
Output is correct |
68 |
Correct |
75 ms |
6092 KB |
Output is correct |
69 |
Correct |
60 ms |
6100 KB |
Output is correct |
70 |
Correct |
65 ms |
6112 KB |
Output is correct |
71 |
Correct |
50 ms |
6108 KB |
Output is correct |
72 |
Correct |
33 ms |
6088 KB |
Output is correct |
73 |
Correct |
37 ms |
6092 KB |
Output is correct |
74 |
Correct |
91 ms |
6116 KB |
Output is correct |
75 |
Correct |
84 ms |
6128 KB |
Output is correct |
76 |
Correct |
91 ms |
6232 KB |
Output is correct |
77 |
Correct |
82 ms |
6104 KB |
Output is correct |
78 |
Correct |
29 ms |
6104 KB |
Output is correct |
79 |
Correct |
74 ms |
6112 KB |
Output is correct |
80 |
Correct |
79 ms |
6096 KB |
Output is correct |
81 |
Correct |
86 ms |
6112 KB |
Output is correct |
82 |
Correct |
79 ms |
6188 KB |
Output is correct |
83 |
Correct |
96 ms |
6104 KB |
Output is correct |
84 |
Correct |
108 ms |
6144 KB |
Output is correct |
85 |
Correct |
92 ms |
6096 KB |
Output is correct |
86 |
Correct |
99 ms |
6148 KB |
Output is correct |
87 |
Correct |
96 ms |
6184 KB |
Output is correct |
88 |
Correct |
100 ms |
6092 KB |
Output is correct |
89 |
Correct |
115 ms |
6100 KB |
Output is correct |
90 |
Correct |
104 ms |
6092 KB |
Output is correct |
91 |
Correct |
103 ms |
6184 KB |
Output is correct |
92 |
Correct |
104 ms |
6172 KB |
Output is correct |