oj.uz

Submission #167161

# Submission time Handle Problem Language Result Execution time Memory
167161 2019-12-06T07:16:55 Z Atill83 Pohlepko (COCI16_pohlepko) C++14
80 / 80
 69 ms 8248 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 2e3+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, m;
char grid[MAXN][MAXN];
queue<pii> q;
vector<pii> yer[26];
bool marked[MAXN][MAXN];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("../IO/int.txt","r",stdin);
        freopen("../IO/out.txt","w",stdout);
    #endif

    cin>>n>>m;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin>>grid[i][j];
        }
    }
    string cur;
    q.push({0, 0});
    cur += grid[0][0];
    //cout<<cur<<endl;
    while(!q.empty()){
        int curR = q.front().ff, curC = q.front().ss;
        //cout<<curR<<" "<<curC<<endl;
        if(curR == n - 1 && curC == m - 1){
            break;
        }
        q.pop();
        if(curR + 1 < n && !marked[curR + 1][curC]){
            yer[(int)(grid[curR + 1][curC] - 'a')].push_back({curR + 1, curC});
            marked[curR + 1][curC] = 1;
        }
        if(curC + 1 < m && !marked[curR][curC + 1]){
            yer[(int)(grid[curR][curC + 1] - 'a')].push_back({curR, curC + 1});
            marked[curR][curC + 1] = 1;
        }

        if(q.empty()){
            int i = 0;
            for(; i < 26; i++){
                if(yer[i].empty()) continue;
                cur = cur +  (char)('a' + i);
                for(pii j: yer[i]){
                    q.push(j);
                }
                yer[i].clear();
                break;
            }
            for(;i < 26;i++){
                yer[i].clear();
            }
        }
    }
    cout<<cur<<endl;
    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 2296 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 7 ms 1784 KB Output is correct
7 Correct 28 ms 5624 KB Output is correct
8 Correct 69 ms 8184 KB Output is correct
9 Correct 3 ms 764 KB Output is correct
10 Correct 4 ms 1144 KB Output is correct
11 Correct 5 ms 888 KB Output is correct
12 Correct 12 ms 4344 KB Output is correct
13 Correct 14 ms 8184 KB Output is correct
14 Correct 69 ms 8248 KB Output is correct
15 Correct 3 ms 760 KB Output is correct
16 Correct 49 ms 8136 KB Output is correct