oj.uz

Submission #1109096

# Submission time Handle Problem Language Result Execution time Memory
1109096 2024-11-06T02:57:17 Z Ryu Pohlepko (COCI16_pohlepko) C++17
15 / 80
 1000 ms 54300 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<char, pair<int, int>>;

const int SZ = 2e5 + 1;
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;
vector<vector<bool>> VIS;
vector<vector<pair<int, int>>> FATHER;
int n, m;

void dijkstra() {
    priority_queue<T, vector<T>, greater<T>> PQ;

    PQ.push({G[1][1], {1, 1}});

    while(!PQ.empty()) {
      int i = PQ.top().S.F, j = PQ.top().S.S;
      char letter = PQ.top().F;
      PQ.pop();

      if(VIS[i][j]) continue;
      VIS[i][j] = 1;
      pair<int, int> a = {0, 0};

      if(i + 1 <= n) {
        PQ.push({G[i + 1][j], {i + 1, j}});

        if(FATHER[i + 1][j] != a) {
          a = FATHER[i + 1][j];

          if(letter < G[a.F][a.S]) {
            FATHER[i + 1][j] = {i, j};
          }
        }
        else {
          FATHER[i + 1][j] = {i, j};
        }
        a = {0, 0};
      }
    
      if(j + 1 <= m) {
        PQ.push({G[i][j + 1], {i, j + 1}});

        if(FATHER[i][j + 1] != a) {
          a = FATHER[i][j + 1];

          if(letter < G[a.F][a.S]) {
            FATHER[i][j + 1] = {i, j};
          }
        }
        else {
          FATHER[i][j + 1] = {i, j};
        }
        a = {0, 0};
      }
    }
}

void word(int i, int j) {
  if(i == 1 && j == 1) {
    cout << char(G[i][j]);
    return;
  }
  word(FATHER[i][j].F, FATHER[i][j].S);
  cout << char(G[i][j]);
}

void solve() {
  cin >> n >> m;

  G.resize(n + 1, vector<char> (m + 1));
  VIS.resize(n + 1, vector<bool> (m + 1));
  FATHER.resize(n + 1, vector<pair<int, int>> (m + 1));

  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= m; j ++) {
      cin >> G[i][j];
    }
  }
   
  dijkstra();

  word(n, m);
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  solve();
  return 0;
}

Subtask #1
15.0 / 80.0

# 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 Incorrect 1 ms 336 KB Output isn't correct
4 Incorrect 2 ms 460 KB Output isn't correct
5 Incorrect 3 ms 592 KB Output isn't correct
6 Incorrect 69 ms 3800 KB Output isn't correct
7 Incorrect 425 ms 20852 KB Output isn't correct
8 Execution timed out 1072 ms 53944 KB Time limit exceeded
9 Incorrect 3 ms 336 KB Output isn't correct
10 Incorrect 17 ms 1360 KB Output isn't correct
11 Incorrect 33 ms 1988 KB Output isn't correct
12 Incorrect 97 ms 4680 KB Output isn't correct
13 Incorrect 51 ms 2896 KB Output isn't correct
14 Execution timed out 1076 ms 54300 KB Time limit exceeded
15 Incorrect 3 ms 592 KB Output isn't correct
16 Correct 236 ms 16320 KB Output is correct