Submission #222027

#	Time	Username	Problem	Language	Result	Execution time	Memory
222027		Haunted_Cpp	Pohlepko (COCI16_pohlepko)	C++17	80 / 80	73 ms	19960 KiB

pohlepko

/*
 author: Haunted_Cpp
 "Persistence guarantees that results are inevitable"
*/
 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
 
const int N = 2e3 + 5;

int step [N][N];
char g [N][N];
char dist [2 * N];

const int dr [] = {+0, +1};
const int dc [] = {+1, +0};

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int r, c;
  cin >> r >> c;
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      cin >> g[i][j];
      step[i][j] = -1;
    }
  }
  for (int i = 0; i < 2 * N; i++) dist[i] = 'z';
  const int K = r + c - 1;
  dist[0] = g[0][0];
  step[0][0] = 0;
  queue<pair<int, int> > q;
  q.push({0, 0});
  while (!q.empty()) {
    int linha = q.front().first;
    int coluna = q.front().second;
    q.pop();
    if (g[linha][coluna] != dist[step[linha][coluna]]) continue;
    for (int i = 0; i < 2; i++) {
      if (linha + dr[i] < 0 || linha + dr[i] >= r || coluna < 0 || coluna + dc[i] >= c) continue;
      if (step[linha + dr[i]][coluna + dc[i]] != -1) continue;
      step[linha + dr[i]][coluna + dc[i]] = step[linha][coluna] + 1;
      dist[step[linha + dr[i]][coluna + dc[i]]] = min (dist[step[linha + dr[i]][coluna + dc[i]]], g[linha + dr[i]][coluna + dc[i]]);
      q.push({linha + dr[i], coluna + dc[i]});
    }
  }
  for (int i = 0; i < K; i++) cout << dist[i];
  cout << '\n';
  return 0;
}

• Subtask 1: 80 / 80