Submission #440357

#	Time	Username	Problem	Language	Result	Execution time	Memory
440357		Karliver	Mecho (IOI09_mecho)	C++14	53 / 100	445 ms	6240 KiB

mecho

	
 #include <bits/stdc++.h>
 
 #define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
 #define all(v) (v).begin(), (v).end()
 using namespace  std;
 #define forn(i,n) for (int i = 0; i < (n); ++i)
 #define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
 using ll = long long;
 int mod = (ll)1e9 + 7;
 #define PI acos(-1)
 typedef pair<int, int> pairs;
 
 const int INF = 1e9 + 1;
 const int N = 2e5 + 100;
 const double eps = 1e-7;
 
 template <class T> using V = vector<T>;  
 template <class T> using VV = V<V<T>>;  
 
 template <typename XPAX>
 void ckma(XPAX &x, XPAX y) {
     x = (x < y ? y : x);
 }
 template <typename XPAX>
 void ckmi(XPAX &x, XPAX y) {
     x = (x > y ? y : x);
 }
 void __print(int x) {cerr << x;}
 void __print(long x) {cerr << x;}
 void __print(long long x) {cerr << x;}
 void __print(unsigned x) {cerr << x;}
 void __print(unsigned long x) {cerr << x;}
 void __print(unsigned long long x) {cerr << x;}
 void __print(float x) {cerr << x;}
 void __print(double x) {cerr << x;}
 void __print(long double x) {cerr << x;}
 void __print(char x) {cerr << '\'' << x << '\'';}
 void __print(const char *x) {cerr << '\"' << x << '\"';}
 void __print(const string &x) {cerr << '\"' << x << '\"';}
 void __print(bool x) {cerr << (x ? "true" : "false");}
 
 template<typename T, typename V>
 void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
 template<typename T>
 void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
 void _print() {cerr << "]\n";}
 template <typename T, typename... V>
 void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
 #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
 void solve() {
 
 
 	
 	int n;
 	cin >> n;
 	int s;
 	cin >> s;

 	queue<pairs> q;

 	V<string> c(n);

 	forn(i, n) {
        cin >> c[i];
        //debug(c[i]);
    }

 	auto valid = [&](int i, int j) {
 		return (i < n && j < n && i > -1 && j > -1 && c[i][j] != 'T');
 	};
    
 	int sx, sy;
 	int tx, ty;
 	V<pairs> directions{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

 	auto dv = [&](int x) {
        return x / s;
    };

 	VV<int> bee(n, V<int>(n, INF));
 	forn(i, n) forn(j, n) {
 		if(c[i][j] == 'H') {
 			q.push({i, j});
 			bee[i][j] = 0;
 		}
 		if(c[i][j] == 'D') {
 			tx = i;
 			ty = j;
 		}
 		if(c[i][j] == 'M') {
 			sx = i;
 			sy = j;
 		}
 	}

   // debug(bee);
 	while(q.size()) {
		int i = q.front().first;
		int j = q.front().second;
		q.pop();
		for(auto dir : directions) {
			int ei = i + dir.first;
			int ej = j + dir.second;

			if(valid(ei, ej) && bee[ei][ej] == INF && c[ei][ej] == 'G') {
				bee[ei][ej] = bee[i][j] + 1;
				q.push({ei, ej});
			}
		}
 	}
   
 	auto ck = [&](int mid) -> bool {
 		VV<int> dis(n, V<int>(n, -1));

 		dis[sx][sy] = 0;
 		queue<pairs> q;

 		q.push({sx, sy});

 		while(q.size()) {
 			int i = q.front().first;
 			int j = q.front().second;
 			q.pop();
 			for(auto dir : directions) {
 				int ei = i + dir.first;
 				int ej = j + dir.second;

 				if(valid(ei, ej) && dis[ei][ej] == -1 && bee[ei][ej] >  dv(dis[i][j] + 1) + mid) {
 					dis[ei][ej] = dis[i][j] + 1;
 					q.push({ei, ej});
 				}
 			}
 		}
        //debug(dis);
 		return (dis[tx][ty] != -1);
 	};


 	int low = 0;
 	int high = 1002;
    
 	while(low < high) {
 		int mid = (low + high + 1) / 2;

 		if(ck(mid))
 			low = mid;
 		else high = mid - 1;
 	}
    
    
 	cout << (ck(low) ? low : -1) << '\n';





 
 
 
 }
 void test_case() {
     int t;
     cin >> t;
     forn(p, t) {
 
         //cout << "Case #" << p + 1 << ": ";
         solve();
     }
 }
 int main() {
 
     ios::sync_with_stdio(false);
     cin.tie(0);
 
     solve();
 
 }
  

• Subtask 1: 53 / 100