제출 #650099

#제출 시각아이디문제언어결과실행 시간메모리
650099mychecksedadMecho (IOI09_mecho)C++17
24 / 100
447 ms65536 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; typedef long long int ll; typedef long double ld; #define MOD (1000000000+7) #define MOD1 (998244353) #define PI 3.1415926535 #define pb push_back #define setp() cout << setprecision(15) #define all(x) x.begin(), x.end() #define debug(x) cerr << #x << " is " << x << '\n'; const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20; int n, S, ax, ay, bx, by, dist[1000][1000], d[1000][1000], arr[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; string s[N]; bool vis[1000][1000]; void solve(){ cin >> n >> S; queue<array<int, 2>> q, q1; for(int i = 0; i < n; ++i){ cin >> s[i]; for(int j = 0; j < n; ++j){ dist[i][j] = d[i][j] = MOD; if(s[i][j] == 'H') q.push({i, j}), dist[i][j] = 0; else if(s[i][j] == 'M') q1.push({i, j}), d[i][j] = 0, bx = i, by = j; else if(s[i][j] == 'D') ax = i, ay = j; } } while(!q.empty()){ int x = q.front()[0], y = q.front()[1]; q.pop(); for(int i = 0; i < 4; ++i){ int a = x + arr[i][0]; int b = y + arr[i][1]; if(a>=0&&a<n&&b>=0&&b<n&&s[a][b]=='D'){ dist[a][b] = min(dist[a][b], dist[x][y] + 1); } if(a<0||b<0||a==n||b==n||(s[a][b]!='G'&&s[a][b]!='M')) continue; if(dist[a][b] > dist[x][y] + 1) { dist[a][b] = dist[x][y] + 1; q.push({a, b}); } } } while(!q1.empty()){ int x = q1.front()[0], y = q1.front()[1]; q1.pop(); for(int i = 0; i < 4; ++i){ for(int f = 1; f <= S; ++f){ int a = x + f * arr[i][0]; int b = y + f * arr[i][1]; if(a<0||b<0||a>=n||b>=n||(s[a][b]!='G'&&s[a][b]!='M'&&s[a][b]!='D')||d[a][b] < d[x][y] + 1) break; d[a][b] = d[x][y] + 1; q1.push({a, b}); } } } int l = 0, r = n*n, ans = -1; while(l <= r){ int m = (l+r)>>1; bool ok = 0; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) vis[i][j] = 0; q.push({ax, ay}); vis[ax][ay] = 1; while(!q.empty()){ int x = q.front()[0], y = q.front()[1]; q.pop(); if(dist[x][y] - m <= d[x][y]){ continue; } if(x == bx && y == by){ ok = 1; break; } for(int i = 0; i < 4; ++i){ for(int f = 1; f <= S; ++f){ int a = x + f * arr[i][0]; int b = y + f * arr[i][1]; if(a<0||b<0||a>=n||b>=n||(s[a][b]!='G'&&s[a][b]!='M')||vis[a][b]) break; vis[a][b] = 1; q.push({a, b}); } } } if(ok){ ans = m; l = m + 1; }else r = m - 1; } cout << ans; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int T = 1, aa; // cin >> T;aa=T; while(T--){ // cout << "Case #" << aa-T << ": "; solve(); cout << '\n'; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'int main()':
mecho.cpp:105:16: warning: unused variable 'aa' [-Wunused-variable]
  105 |     int T = 1, aa;
      |                ^~
#Verdict Execution timeMemoryGrader output
Fetching results...