oj.uz

Submission #371229

# Submission time Handle Problem Language Result Execution time Memory
371229 2021-02-26T08:21:02 Z maozkurt Pohlepko (COCI16_pohlepko) C++17
0 / 80
 1000 ms 45036 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <numeric>
#include <cassert>

#define endl '\n'
#define sp ' '

#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn = 2005;

char arr[maxn][maxn];
int d[maxn][maxn];
int p[maxn][maxn];
const int inf = 1e9;
int n,m;
void dijkstra(){
    using paa = pair<int,pii>;
    priority_queue<paa,vector<paa>,greater<paa>> q;
    
    fill(&d[0][0],&d[n-1][m-1] + 1,inf);
    d[0][0] = 0;
    q.push({0,{0,0}});

    while(q.size()){
        int curd = q.top().ff;
        int curi = q.top().ss.ff;
        int curj = q.top().ss.ss;
        q.pop();
        if(curd != d[curi][curj])
            continue;

        if(curi<n-1){
            if(d[curi+1][curj] > d[curi][curj] + arr[curi][curj]){
                d[curi+1][curj] = d[curi][curj] + arr[curi][curj];
                q.push({d[curi+1][curj],{curi+1,curj}});
                p[curi+1][curj] = 1;
            }
        }

        if(curj<m-1){
            if(d[curi][curj+1] > d[curi][curj] + arr[curi][curj]){
                d[curi][curj+1] = d[curi][curj] + arr[curi][curj];
                q.push({d[curi][curj+1],{curi,curj+1}});
                p[curi][curj+1] = -1;
            }
        }
    }
}

int main(){
    
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cerr.tie(nullptr);
    
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin >> arr[i];
    
    dijkstra();
    

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout << p[i][j] << sp;
        }
        cout << endl;
    }    
    int i=n-1,j=m-1;
    string ans;
    ans += arr[i][j];
    while(i!=0 || j!=0){
        if(p[i][j] == 1){
            ans.pb((char)(d[i][j] - d[i-1][j]));
            i--;
        }
        else if(p[i][j] == -1){
            ans.pb((char)(d[i][j] - d[i][j-1]));
            j--;
        }
        else
            abort();
    }
    for(int c=(int)ans.size()-1;c>=0;c--){
        cout << ans[c];
    }
    cout << endl;
    
}

Subtask #1
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Incorrect 5 ms 7276 KB Output isn't correct
3 Incorrect 1 ms 492 KB Output isn't correct
4 Incorrect 1 ms 1004 KB Output isn't correct
5 Incorrect 2 ms 620 KB Output isn't correct
6 Incorrect 63 ms 6892 KB Output isn't correct
7 Incorrect 403 ms 28652 KB Output isn't correct
8 Execution timed out 1044 ms 42348 KB Time limit exceeded
9 Incorrect 3 ms 1772 KB Output isn't correct
10 Incorrect 17 ms 3564 KB Output isn't correct
11 Incorrect 31 ms 3108 KB Output isn't correct
12 Incorrect 90 ms 16620 KB Output isn't correct
13 Incorrect 57 ms 29420 KB Output isn't correct
14 Execution timed out 1100 ms 45036 KB Time limit exceeded
15 Incorrect 4 ms 1900 KB Output isn't correct
16 Incorrect 339 ms 31724 KB Output isn't correct