oj.uz

Submission #864354

# Submission time Handle Problem Language Result Execution time Memory
864354 2023-10-22T15:24:34 Z lalig777 Pohlepko (COCI16_pohlepko) C++14
65 / 80
 1000 ms 65536 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct info{
    int fila;
    int columna;
    int nivel;
    char letra;
};

string bfs(int n, int m, vector<vector<char>>tablero){
    int nivelactual=0;
    string s="";
    s+=tablero[0][0];
    queue<info>cola;
    info primero;
    primero.fila=1;
    primero.columna=0;
    primero.nivel=1;
    primero.letra=s[0];
    cola.push(primero);
    primero.fila=0;
    primero.columna=1;
    cola.push(primero);
    while (!cola.empty()){
        int i_actual=cola.front().fila;
        int j_actual=cola.front().columna;
        if (i_actual==n or j_actual==m){
            cola.pop();
            continue;
        }if (cola.front().nivel!=nivelactual){
            nivelactual++;
            s+='z';
        }if (s[nivelactual-1]==cola.front().letra){
            if (s[nivelactual]>=tablero[i_actual][j_actual]){
                s[nivelactual]=tablero[i_actual][j_actual];
                info casilla;
                casilla.fila=i_actual+1;
                casilla.columna=j_actual;
                casilla.nivel=nivelactual+1;
                casilla.letra=s[nivelactual];
                cola.push(casilla);
                casilla.fila--;
                casilla.columna++;
                cola.push(casilla);
            }
        }cola.pop();
    }return s;
}

int main(){
    int n, m;
    cin>>n>>m;
    vector<vector<char>>tablero(n, vector<char>(m));
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++) cin>>tablero[i][j];
    }cout<<bfs(n, m, tablero)<<'\n';
    return 0;
}

Subtask #1
65.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 8 ms 940 KB Output is correct
7 Correct 43 ms 3152 KB Output is correct
8 Correct 140 ms 8240 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 6 ms 604 KB Output is correct
11 Correct 13 ms 604 KB Output is correct
12 Correct 13 ms 1116 KB Output is correct
13 Correct 12 ms 860 KB Output is correct
14 Execution timed out 1092 ms 34868 KB Time limit exceeded
15 Runtime error 100 ms 65536 KB Execution killed with signal 9
16 Runtime error 168 ms 65536 KB Execution killed with signal 9