제출 #222025

#제출 시각아이디문제언어결과실행 시간메모리
222025Haunted_CppPohlepko (COCI16_pohlepko)C++17
55 / 80
73 ms20960 KiB
/* 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 [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 < 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...