Submission #167161

#	Time	Username	Problem	Language	Result	Execution time	Memory
167161		Atill83	Pohlepko (COCI16_pohlepko)	C++14	80 / 80	69 ms	8248 KiB

pohlepko

#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 / 80