oj.uz

Submission #1106764

# Submission time Handle Problem Language Result Execution time Memory
1106764 2024-10-31T03:20:34 Z vjudge1 Pohlepko (COCI16_pohlepko) C++14
10 / 80
 1000 ms 43776 KB 
#include <bits/stdc++.h>
#define sts(v) svble_sort(v.BE, v.E)
#define Rsts(v) svble_sort(v.rBE, v.rE)
#define rev(v) reverse(v.BE, v.E)
#define BE begin()
#define rBE rbegin()
#define E end()
#define rE rend()
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define F first
#define S second

using namespace std;
using ll = long long;

const int MAXN = 2e3 + 1;
const int MOD = 1e9 + 7;

char v[MAXN][MAXN];
pair<int, int> ans[MAXN][MAXN];
bool cmp[MAXN][MAXN];
int n, m;

void dij(){
    priority_queue<pair<int, pair<pair<char, pair<int, int>>, pair<int, int>>>> q;
    q.push({1, {{v[1][1], {-1, -1}}, {1, 1}}});

    while(q.size()){
        int x = q.top().S.S.F, y = q.top().S.S.S, cnt = abs(q.top().F);
        pair<int, int> anterior = q.top().S.F.S;
        char c = abs(q.top().S.F.F);
        q.pop();

        if(x > n or y > m or cmp[x][y])continue;
        cmp[x][y] = 1;
        ans[x][y] = anterior;

        q.push({-(cnt + 1), {{-v[x][y], {x, y}}, {x + 1, y}}});
        q.push({-(cnt + 1), {{-v[x][y], {x, y}}, {x, y + 1}}});
    }
}

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

    cin >> n >> m;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            char c; cin >> c;

            v[i][j] = c;
        }

    dij();

    string res = "";
    

    while(n > 0){
        res.pb(v[n][m]);
        int N = ans[n][m].F, M = ans[n][m].S;
        n = N; m = M;
    }
    rev(res);

    cout << res << '\n';

    return 0;
}

Compilation message

pohlepko.cpp: In function 'void dij()':
pohlepko.cpp:34:14: warning: unused variable 'c' [-Wunused-variable]
   34 |         char c = abs(q.top().S.F.F);
      |              ^

Subtask #1
10.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 2 ms 13648 KB Output is correct
3 Incorrect 1 ms 4432 KB Output isn't correct
4 Incorrect 2 ms 6628 KB Output isn't correct
5 Incorrect 3 ms 4432 KB Output isn't correct
6 Incorrect 66 ms 11600 KB Output isn't correct
7 Incorrect 374 ms 32888 KB Output isn't correct
8 Execution timed out 1060 ms 43776 KB Time limit exceeded
9 Incorrect 3 ms 6736 KB Output isn't correct
10 Incorrect 16 ms 9292 KB Output isn't correct
11 Incorrect 29 ms 7160 KB Output isn't correct
12 Incorrect 104 ms 25244 KB Output isn't correct
13 Incorrect 49 ms 39812 KB Output isn't correct
14 Execution timed out 1053 ms 43660 KB Time limit exceeded
15 Incorrect 4 ms 6736 KB Output isn't correct
16 Incorrect 347 ms 35160 KB Output isn't correct