oj.uz

Submission #166837

# Submission time Handle Problem Language Result Execution time Memory
166837 2019-12-04T09:05:48 Z sans Pohlepko (COCI16_pohlepko) C++14
40 / 80
 1000 ms 51884 KB 
#include <iostream>
#include <numeric>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <set>
#include <map>

using namespace std;

#define sp ' '
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define forn(YY, yy) for(long long int yy = 0; yy < YY; ++yy)
#define prn(XX) cout << XX << endl
#define prs(XX) cout << XX << " "

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const int MOD = 1e9 + 7;
const int INF = 2e9 + 13;
const int mINF = -2e9 - 13;
const double PI = 3.14159265358979;
const double EPS = 1e-9;

int N, M;
vector<vector<char>> grid;
map<pair<int, int>, bool> visited;

int main(int argc, char **argv){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;
    grid.resize(N, vector<char>(M));

    for(int i = 0; i < N; ++i) for(int j = 0; j < M; ++j) cin >> grid[i][j];

    queue<pair<string, pair<int, int>>> q; string s; s += grid[0][0];
    q.push(mp(s, mp(0, 0)));

    set<string> Set;
    while(!q.empty()){
        pair<string, pair<int, int>> t = q.front(); q.pop();
        int x = t.nd.st, y = t.nd.nd;

        if(x == N-1 and y == M-1){ Set.insert(t.st); continue; }

        if(x < N-1 and y < M-1){
            if(grid[x][y+1] < grid[x+1][y]){
                if(!visited[mp(x, y+1)]){
                    visited[mp(x, y+1)] = true;
                    q.push(mp(t.st + grid[x][y+1], mp(x, y+1)));
                }
            }
            else if(grid[x][y+1] > grid[x+1][y]){
                if(!visited[mp(x+1, y)]){
                    visited[mp(x+1, y)] = true;
                    q.push(mp(t.st + grid[x+1][y], mp(x+1, y)));
                }
            }
            else{
                if(!visited[mp(x+1, y)]){
                    visited[mp(x+1, y)] = true;
                    q.push(mp(t.st + grid[x+1][y], mp(x+1, y)));
                }
                if(!visited[mp(x, y+1)]){
                    visited[mp(x, y+1)] = true;
                    q.push(mp(t.st + grid[x][y+1], mp(x, y+1)));
                }
            }
        }

        else if(x >= N-1 and y < M-1){
            if(!visited[mp(x, y+1)]){
                visited[mp(x, y+1)] = true;
                q.push(mp(t.st + grid[x][y+1], mp(x, y+1)));
            }
        }
        else if(x < N-1 and y >= M-1){
            if(!visited[mp(x+1, y)]){
                visited[mp(x+1, y)] = true;
                q.push(mp(t.st + grid[x+1][y], mp(x+1, y)));
            }
        }
    }

    cout << *(Set.begin()) << endl;

    return 0;
}

//cikisir

Subtask #1
40.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 7 ms 888 KB Output is correct
7 Correct 26 ms 3192 KB Output is correct
8 Correct 71 ms 8492 KB Output is correct
9 Incorrect 2 ms 376 KB Output isn't correct
10 Incorrect 5 ms 632 KB Output isn't correct
11 Incorrect 5 ms 760 KB Output isn't correct
12 Incorrect 10 ms 1272 KB Output isn't correct
13 Incorrect 7 ms 888 KB Output isn't correct
14 Incorrect 182 ms 14040 KB Output isn't correct
15 Incorrect 15 ms 1400 KB Output isn't correct
16 Execution timed out 1076 ms 51884 KB Time limit exceeded