結果
問題 | No.2731 Two Colors |
ユーザー |
![]() |
提出日時 | 2024-04-19 21:46:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 246 ms / 3,000 ms |
コード長 | 2,545 bytes |
コンパイル時間 | 2,141 ms |
コンパイル使用メモリ | 181,016 KB |
実行使用メモリ | 11,760 KB |
最終ジャッジ日時 | 2024-10-11 14:40:35 |
合計ジャッジ時間 | 6,444 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:60:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 60 | auto [val, x, y] = que0.top(); | ^ main.cpp:82:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 82 | auto [val, x, y] = que1.top(); | ^
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;constexpr ll mod = 998244353;template<ll mod>struct Mint {using M=Mint; ll v;M& put(ll x) { v=(x<mod)?x:x-mod; return *this; }Mint(ll x=0) { put(x%mod+mod); }M operator+(M m) {return M().put(v+m.v);}M operator-(M m) {return M().put(v+mod-m.v);}M operator*(M m) {return M().put(v*m.v%mod);}M operator/(M m) {return M().put(v*m.inv().v%mod);}// BEGIN IGNOREM operator+=(M m) { return put(v+m.v); }M operator-=(M m) { return put(v+mod-m.v); }M operator*=(M m) { return put(v*m.v%mod); }M operator/=(M m) { return put(v*m.inv().v%mod); }// END IGNOREbool operator==(M m) { return v==m.v; }M pow(ll m) const {M x=v, res=1;while (m) {if (m&1) res=res*x;x=x*x; m>>=1;}return res;}M inv() { return pow(mod-2); }};using mint = Mint<mod>;int main(){cin.tie(0);cin.sync_with_stdio(0);int h, w;cin >> h >> w;vector<vector<int>> a(h, vector<int>(w));for(int i = 0; i < h; ++i){for(int j = 0; j < w; ++j){cin >> a[i][j];}}vector<vector<int>> state(h, vector<int>(w, -1));priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> que0, que1;que0.emplace(a[0][0], 0, 0);que1.emplace(a[h-1][w-1], h - 1, w - 1);vector<int> dx{0, 1, 0, -1};vector<int> dy{1, 0, -1, 0};int j;for(j = 0; j < h * w - 2; ++j){if(j % 2 == 0){while(!que0.empty()){auto [val, x, y] = que0.top();que0.pop();if(state[x][y] != -1)continue;state[x][y] = 0;for(int d = 0; d < 4; ++d){int nx = x + dx[d];int ny = y + dy[d];if(nx < 0 || ny < 0 || nx >= h || ny >= w)continue;if(state[nx][ny] == 0)continue;if(state[nx][ny] == 1){cout << j - 1 << endl;exit(0);}que0.emplace(a[nx][ny], nx, ny);}break;}}else{while(!que1.empty()){auto [val, x, y] = que1.top();que1.pop();if(state[x][y] != -1)continue;state[x][y] = 1;for(int d = 0; d < 4; ++d){int nx = x + dx[d];int ny = y + dy[d];if(nx < 0 || ny < 0 || nx >= h || ny >= w)continue;if(state[nx][ny] == 1)continue;if(state[nx][ny] == 0){cout << j - 1 << endl;exit(0);}que1.emplace(a[nx][ny], nx, ny);}break;}}}}