// author : anhtun_hi , nqg
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define reset(h, v) memset(h, v, sizeof h)
#define Forv(i, a) for(auto& i : a)
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define c_bit(i) __builtin_popcountll(i)
#define Bit(mask, i) ((mask >> i) & 1LL)
#define onbit(mask, i) ((mask) bitor (1LL << i))
#define offbit(mask, i) ((mask) &~ (1LL << i))
using namespace std;
namespace std {
template <typename T, int D>
struct _vector : public vector <_vector <T, D - 1>> {
static_assert(D >= 1, "Dimension must be positive!");
template <typename... Args>
_vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
};
template <typename T> struct _vector <T, 1> : public vector <T> {
_vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
};
template <class A, class B> bool minimize(A &a, B b){return a > b ? a = b, true : false;}
template <class A, class B> bool maximize(A &a, B b){return a < b ? a = b, true : false;}
}
const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0}, LOG = 20, base = 311, inf = 1e9 + 5;
const int MAXN = 1e6 + 5;
const ll mod = 1e9 + 7;
const ll oo = 1e18;
#define int long long
int n, m;
vector<vector<char>> a;
//vector<vector<char>> d;
char d[1000000 + 5];
vector<vector<bool>> vs, ok;
vector<vector<ii>> trace;
struct Node{
int x, y; char val;
};
struct cmp {
bool operator() (const Node &A, const Node &B) {
if(A.x + A.y == B.x + B.y) return A.val - 'a' > B.val - 'a';
return A.x + A.y > B.x + B.y;
}
};
void Solve() {
cin >> n >> m;
a.resize(n + 5, vector<char>(m + 5));
vs.resize(n + 5, vector<bool>(m + 5, 0));
ok.resize(n + 5, vector<bool>(m + 5, 0));
For(i, 1, n) For(j, 1, m) {
cin >> a[i][j];
if(a[i][j] == '#') a[i][j] = '{';
d[i + j - 1] = '{';
}
queue<ii> q;
q.push({n, m});
while(q.size()){
auto [x, y] = q.front();
vs[x][y] = true;
q.pop();
for (int k : {0, 3}){
int u = x + dx[k];
int v = y + dy[k];
if(1 <= u && u <= n && 1 <= v && v <= m && a[u][v] != '{'){
if(!vs[u][v]) vs[u][v] = true, q.push({u, v});
}
}
}
priority_queue<Node, vector<Node>, cmp> pq;
pq.push({1, 1, a[1][1]});
while(pq.size()){
auto [x, y, val] = pq.top(); pq.pop();
if (d[x + y - 1] == '{') {
d[x + y - 1] = val;
}
else if (a[x][y] != d[x + y - 1]) continue;
ok[x][y] = true;
for(int k : {1, 2}){
int u = x + dx[k];
int v = y + dy[k];
if(1 <= u && u <= n && 1 <= v && v <= m && vs[u][v] == true){
if (!ok[u][v]){
ok[u][v] = true;
pq.push({u, v, a[u][v]});
}
}
}
}
For(i, 1, n + m - 1) cout << d[i];
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(0);
if(fopen("b.inp", "r")) {
freopen("b.inp", "r", stdin);
freopen("b.out", "w", stdout);
}
int t = 1;
// cin >> t;
for (int test = 1; test <= t; test++) {
Solve();
}
return 0;
}
Compilation message
pohlepko.cpp: In function 'void Solve()':
pohlepko.cpp:68:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
68 | auto [x, y] = q.front();
| ^
pohlepko.cpp:82:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
82 | auto [x, y, val] = pq.top(); pq.pop();
| ^
pohlepko.cpp: In function 'int32_t main()':
pohlepko.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | freopen("b.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
pohlepko.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | freopen("b.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
7 ms |
1064 KB |
Output is correct |
| 7 |
Correct |
41 ms |
3656 KB |
Output is correct |
| 8 |
Correct |
108 ms |
9544 KB |
Output is correct |
| 9 |
Correct |
1 ms |
592 KB |
Output is correct |
| 10 |
Correct |
2 ms |
592 KB |
Output is correct |
| 11 |
Correct |
4 ms |
592 KB |
Output is correct |
| 12 |
Correct |
10 ms |
1360 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1272 KB |
Output is correct |
| 14 |
Correct |
93 ms |
9520 KB |
Output is correct |
| 15 |
Correct |
2 ms |
336 KB |
Output is correct |
| 16 |
Correct |
95 ms |
4148 KB |
Output is correct |
