oj.uz

Submission #1109563

# Submission time Handle Problem Language Result Execution time Memory
1109563 2024-11-07T03:47:26 Z Zero_OP Pohlepko (COCI16_pohlepko) C++14
80 / 80
 58 ms 21320 KB 
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    vector<vector<char>> a(N, vector<char>(M));
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < M; ++j){
            cin >> a[i][j];
        }
    }

    vector<vector<int>> par(N, vector<int>(M, -1));

    //0 : (-1, 0)
    //1 : (0, -1)

    queue<tuple<int, int, int>> q;
    q.push({0, 0, 0});

    const int dx[2] = {0, 1};
    const int dy[2] = {1, 0};

    vector<pair<int, int>> cand;
    cand.push_back({0, 0});

    while(!cand.empty()){
        vector<pair<int, int>> new_cand;

        cout << a[cand[0].first][cand[0].second];
        if(cand[0] == make_pair(N - 1, M - 1)){
            break;
        }

        int best = -1;

        for(auto [x, y] : cand){
            for(int i = 0; i < 2; ++i){
                int nx = x + dx[i], ny = y + dy[i];
                if(nx < N && ny < M){
                    int c = a[nx][ny] - 'a';
                    if(best == -1 || best > c){
                        best = c;
                        new_cand.clear();
                        new_cand.emplace_back(nx, ny);
                    } else if(best == c) new_cand.emplace_back(nx, ny);
                }
            }
        }

        sort(new_cand.begin(), new_cand.end());
        new_cand.erase(unique(new_cand.begin(), new_cand.end()), new_cand.end());

        swap(cand, new_cand);
    }

    return 0;
}

Compilation message

pohlepko.cpp: In function 'int main()':
pohlepko.cpp:43:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |         for(auto [x, y] : cand){
      |                  ^

Subtask #1
80.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 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 4 ms 1480 KB Output is correct
7 Correct 17 ms 8016 KB Output is correct
8 Correct 46 ms 20040 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 2 ms 1104 KB Output is correct
12 Correct 5 ms 2128 KB Output is correct
13 Correct 3 ms 1360 KB Output is correct
14 Correct 58 ms 21320 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 41 ms 8776 KB Output is correct