結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 2024-04-19 21:53:50 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 170 ms / 3,000 ms |
コード長 | 2,691 bytes |
コンパイル時間 | 3,211 ms |
コンパイル使用メモリ | 264,884 KB |
実行使用メモリ | 15,104 KB |
最終ジャッジ日時 | 2024-10-11 14:53:50 |
合計ジャッジ時間 | 7,065 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <class F, class S>ostream &operator<<(ostream &s, const pair<F, S> &v) {s << "(" << v.first << ", " << v.second << ")";return s;}template <ranges::range T,class = enable_if_t<!is_convertible_v<T, string_view>>>istream &operator>>(istream &s, T &&v) {for (auto &&x : v) s >> x;return s;}template <ranges::range T,class = enable_if_t<!is_convertible_v<T, string_view>>>ostream &operator<<(ostream &s, T &&v) {for (auto &&x : v) s << x << ' ';return s;}#ifdef LOCALtemplate <class... T> void dbg(T... x) {char e{};((cerr << e << x, e = ' '), ...);}#define debug(x...) dbg(#x, '=', x, '\n')#else#pragma GCC optimize("O3,unroll-loops")#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")#define debug(...) ((void)0)#endif#define all(v) (v).begin(), (v).end()#define rall(v) (v).rbegin(), (v).rend()#define ff first#define ss secondtemplate <class T> inline constexpr T inf = numeric_limits<T>::max() / 2;template <class T> bool chmin(T &a, T b) { return (b < a and (a = b, true)); }template <class T> bool chmax(T &a, T b) { return (a < b and (a = b, true)); }using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;using i128 = __int128;constexpr i64 mod = 998244353;void solve() {int n, m;cin >> n >> m;vector A(n, vector<int>(m));cin >> A;vector vis(n, vector<int>(m, -1));vector inque(n, vector<int>(m, 0));priority_queue<array<int, 3>> pq[2]{};pq[0].push({-A[0][0], 0, 0});pq[1].push({-A[n - 1][m - 1], n - 1, m - 1});inque[0][0] = 1;inque[n - 1][m - 1] = 2;const vector<pair<int, int>> dir{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};auto safe = [&](int x, int y) -> bool {return 0 <= x and x < n and 0 <= y and y < m;};int ans = 0;for (int cur = 0; ; cur ^= 1) {ans++;auto [_, x, y] = pq[cur].top();pq[cur].pop();vis[x][y] = cur;for (auto [dx, dy] : dir) {int nx = x + dx;int ny = y + dy;if (safe(nx, ny)) {if (vis[nx][ny] == (cur ^ 1)) {cout << ans - 2 << '\n';return;}if (~inque[nx][ny] >> cur & 1) {inque[nx][ny] |= (1 << cur);pq[cur].push({-A[nx][ny], nx, ny});}}}}}signed main() {cin.tie(0)->sync_with_stdio(false);cin.exceptions(cin.failbit);int t = 1;// cin >> t;while (t--) {solve();}return 0;}