oj.uz

Submission #1109809

# Submission time Handle Problem Language Result Execution time Memory
1109809 2024-11-07T16:16:22 Z Ryu Pohlepko (COCI16_pohlepko) C++17
80 / 80
 45 ms 12872 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define LL long long
 
#define rep(i, x) for(auto &i : (x))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
#define left(x) ((x)<<1)
#define right(x) ((x)>>1)
#define LSOne(x) (x & -(x))
 
using namespace std;
using T = pair<pair<int,char>, pair<int, int>>;
 
const int SZ = 2e3 + 10;
const LL MOD = 1e9 + 7; 
const LL INF = 1e18 + 1;
 
LL bp (LL b, LL e, LL m = MOD) {
 if ( e == 0 ) return 1;
 LL T = bp(b, e / 2);
 T *= T; T %= m;
 if ( e & 1 ) T *= b;
 return T %= m;
}
 
LL nv_i (LL a) { return bp(a, MOD - 2); };
LL gcd (LL a, LL b) { return (b == 0 ? a : gcd(b, a % b)); }
LL lcm(LL a, LL b) { return (a * (b / gcd(a, b))); }
LL ceil (LL a, LL b) { return ((a + b - 1) / b); }
 
vector<vector<char>> G(SZ, vector<char> (SZ));
vector<vector<bool>> VIS(SZ, vector<bool> (SZ));
vector<char> LETTERS(SZ * SZ + 1, 'z' + 1);
int n, m;
int bfs() {
queue<T> Q;
int mx = 0;
Q.push({{1, 'z' + 1}, {1, 1}});
 
  while(!Q.empty()) {
    int dist = Q.front().F.F, i = Q.front().S.F, j = Q.front().S.S, prev_l = Q.front().F.S;
    Q.pop();
 
    if(VIS[i][j] || i > n || j > m || LETTERS[dist - 1] != prev_l) continue;
    VIS[i][j] = 1;
    
    LETTERS[dist] = min(LETTERS[dist], G[i][j]);
mx = max(mx, dist);
    Q.push({{dist + 1, G[i][j]}, {i + 1, j}});
    Q.push({{dist + 1, G[i][j]}, {i, j + 1}});
  }return mx;
}
 
void solve() {
  cin >> n >> m;
 
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= m; j ++) {
      char x;
      cin >> x;
      
      G[i][j] = x;
    }
  } 
 
int mx = bfs();
 
  for(int i = 1; i <= mx; i ++) {
    cout << LETTERS[i];
  }
}
 
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
 
  solve();
  return 0;
}

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9040 KB Output is correct
2 Correct 6 ms 9040 KB Output is correct
3 Correct 6 ms 8992 KB Output is correct
4 Correct 6 ms 9040 KB Output is correct
5 Correct 6 ms 9040 KB Output is correct
6 Correct 9 ms 9184 KB Output is correct
7 Correct 20 ms 10320 KB Output is correct
8 Correct 45 ms 12692 KB Output is correct
9 Correct 7 ms 9040 KB Output is correct
10 Correct 7 ms 9040 KB Output is correct
11 Correct 8 ms 9040 KB Output is correct
12 Correct 10 ms 9200 KB Output is correct
13 Correct 10 ms 9040 KB Output is correct
14 Correct 44 ms 12872 KB Output is correct
15 Correct 7 ms 9208 KB Output is correct
16 Correct 36 ms 10412 KB Output is correct