oj.uz

Submission #1109029

# Submission time Handle Problem Language Result Execution time Memory
1109029 2024-11-05T19:52:15 Z Ryu Pohlepko (COCI16_pohlepko) C++17
20 / 80
 766 ms 65096 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<int, 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<int>> G, DIS;
vector<vector<pair<int, int>>> FATHER;
vector<vector<bool>> VIS;
int n, m;

void dijkstra() {
  priority_queue<T, vector<T>, greater<T>> PQ;
  PQ.push({0, {1, 1}});

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

    if(VIS[i][j]) continue;
    VIS[i][j] = 1;


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

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<int> (m + 1));
  DIS.resize(n + 1, vector<int> (m + 1, 1e9));
  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 ++) {
      char x;
      cin >> x;

      G[i][j] = int(x);
    }
  }
  
  
  DIS[1][1] = 0;
  dijkstra();

  word(n, m);
}

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

  solve();
  return 0;
}

Subtask #1
20.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 1 ms 336 KB Output isn't correct
5 Incorrect 1 ms 592 KB Output isn't correct
6 Incorrect 33 ms 4176 KB Output isn't correct
7 Incorrect 213 ms 21840 KB Output isn't correct
8 Incorrect 766 ms 65096 KB Output isn't correct
9 Incorrect 1 ms 336 KB Output isn't correct
10 Incorrect 11 ms 1484 KB Output isn't correct
11 Incorrect 13 ms 2384 KB Output isn't correct
12 Incorrect 47 ms 5712 KB Output isn't correct
13 Incorrect 20 ms 4088 KB Output isn't correct
14 Incorrect 739 ms 65052 KB Output isn't correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 165 ms 25620 KB Output is correct