oj.uz

Submission #864388

# Submission time Handle Problem Language Result Execution time Memory
864388 2023-10-22T16:51:13 Z Ariadna Pohlepko (COCI16_pohlepko) C++14
65 / 80
 1000 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

int n, m;
vector < vector < char > > grid;

void bfs() {
    queue < pair < pair < int, int >, int > > q;
    q.push(make_pair(make_pair(0, 0), 0));
    vector < char > min_char(n + m - 1, 'z');
    min_char[0] = grid[0][0];
    while (!q.empty()) {
        int i = q.front().first.first;
        int j = q.front().first.second;
        int d = q.front().second;
        q.pop();
        if (grid[i][j] != min_char[d]) continue;
        if (i < n - 1) {
            q.push(make_pair(make_pair(i + 1, j), d + 1));
            min_char[d + 1] = min(min_char[d + 1], grid[i + 1][j]);
        }
        if (j < m - 1) {
            q.push(make_pair(make_pair(i, j + 1), d + 1));
            min_char[d + 1] = min(min_char[d + 1], grid[i][j + 1]);
        }
    }
    for (int i = 0; i < n + m - 1; ++i) {
        cout << min_char[i];
    }
    cout << '\n';
}

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

Subtask #1
65.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 604 KB Output is correct
7 Correct 43 ms 1628 KB Output is correct
8 Correct 133 ms 4404 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Correct 9 ms 556 KB Output is correct
12 Correct 12 ms 604 KB Output is correct
13 Correct 8 ms 604 KB Output is correct
14 Execution timed out 1099 ms 23768 KB Time limit exceeded
15 Runtime error 126 ms 65536 KB Execution killed with signal 9
16 Runtime error 174 ms 65536 KB Execution killed with signal 9