oj.uz

Submission #1109026

# Submission time Handle Problem Language Result Execution time Memory
1109026 2024-11-05T19:35:30 Z vjudge1 Pohlepko (COCI16_pohlepko) C++17
20 / 80
 742 ms 65536 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 31 ms 4352 KB Output isn't correct
7 Incorrect 208 ms 21832 KB Output isn't correct
8 Incorrect 742 ms 65536 KB Output isn't correct
9 Incorrect 1 ms 336 KB Output isn't correct
10 Incorrect 8 ms 1360 KB Output isn't correct
11 Incorrect 18 ms 2384 KB Output isn't correct
12 Incorrect 45 ms 5712 KB Output isn't correct
13 Incorrect 18 ms 3920 KB Output isn't correct
14 Incorrect 713 ms 65536 KB Output isn't correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 156 ms 25680 KB Output is correct