| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 923671 | josanneo22 | Mecho (IOI09_mecho) | C++17 | 253 ms | 3932 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.
#pragma warning(suppress : 4996)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
// char buf[1 << 23], * p1 = buf, * p2 = buf;
// #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template<typename T> inline void read(T& x) { x = 0; T f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * (1 << 1) + x * (1 << 3) + (ch - 48); ch = getchar(); } x *= f; }
template<typename x, typename... y>void read(x& a, y&... b) { read(a); read(b...); }
template<typename T> inline void print(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) print(x / 10); putchar(x % 10 + '0'); }
template<typename x, typename... y>void print(x& a, y&... b) { print(a); putchar(' '); print(b...); }
#define spa putchar(' ')
#define nl putchar('\n')
#define printv(a) for(int p = 0; p < a.size(); p++) print(a[p]), (p == a.size() - 1? nl : sp);
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define all(x) x.begin(),x.end()
#define me(x,a) memset(x,a,sizeof(x))
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int N, S; cin >> N >> S;
vector<vector<char>> G(N + 1, vector<char>(N + 1));
vector<vector<int>> dis(N + 1, vector<int>(N + 1, -1));
int init_x, init_y, end_x, end_y;
queue<pair<int, int>> q;
L(i, 1, N) L(j, 1, N) {
cin >> G[i][j];
if (G[i][j] == 'M') {
init_x = i, init_y = j;
G[i][j] == 'G';
}
if (G[i][j] == 'D') {
end_x = i, end_y = j;
G[i][j] == 'G';
}
if (G[i][j] == 'H') {
dis[i][j] = 0;
q.push(make_pair(i, j));
}
}
auto can_go = [&](int x, int y) { return x >= 1 && x <= N && y >= 1 && y <= N && G[x][y] != 'T'; };
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1, -1, 0,0 };
while (q.size()) {
int x = q.front().first, y = q.front().second; q.pop();
for (int dir = 0; dir < 4; dir++) {
int xx = x + dx[dir], yy = y + dy[dir];
if (can_go(xx, yy) && dis[xx][yy] == -1) {
dis[xx][yy] = dis[x][y] + S;
q.push(make_pair(xx, yy));
}
}
}
dis[end_x][end_y] = N * N * S + 1;
function<bool(int)> check = [&](int T) {
if (T * S >= dis[init_x][init_y]) return false;
queue<pair<int, pair<int, int>>> Q;
vector<vector<bool>> vis(N + 1, vector<bool>(N + 1));
Q.push(make_pair(T * S, make_pair(init_x, init_y)));
vis[init_x][init_y] = true;
while (Q.size()) {
int d = Q.front().first;
int x = Q.front().second.first, y = Q.front().second.second;
Q.pop();
if (x == end_x && y == end_y) return true;
for (int dir = 0; dir < 4; dir++) {
int xx = x + dx[dir], yy = y + dy[dir];
if (can_go(xx, yy) && !vis[xx][yy] && (d + 1 < dis[xx][yy])) {
Q.push(make_pair(d + 1, make_pair(xx, yy)));
vis[xx][yy] = true;
}
}
}
return false;
};
int lo = 0, hi = 2 * N * N, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (check(mid)) {
ans = mid;
lo = mid + 1;
}
else hi = mid - 1;
}
cout << ans << '\n';
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||