oj.uz

Submission #1091829

# Submission time Handle Problem Language Result Execution time Memory
1091829 2024-09-22T10:08:01 Z Jakub_Wozniak Tracks in the Snow (BOI13_tracks) C++14
91.25 / 100
 2000 ms 79804 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4009;
typedef long long ll;
int N , M;
string s[maxn];
int a , b , c;
vector <pair<int,int>> R;
bool vis[maxn][maxn];
int MAXI = 0;

void pr()
{
    R.push_back({-1,0});
    R.push_back({1,0});
    R.push_back({0,1});
    R.push_back({0,-1});
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for(int i = 0 ; i <= M+1 ; i++ )s[0].push_back( '.');
    for(int i = 0 ; i <= M+1 ; i++ )s[N+1].push_back('.');

    pr();
    for(int i = 1 ; i <= N  ;i++)
    {
        cin >> s[i];
        s[i] = '.'+s[i];
        s[i].push_back('.');
    }

    priority_queue <pair<int,int>> q;
    pair<int,int> DS;
    q.push({-1,1*maxn+1});
    int i , j;
    vis[1][1] = 1;

    while(!q.empty())
    {
        DS = q.top();
        c = -DS.first; 
        i = DS.second/maxn;
        j = DS.second%maxn;
        q.pop();
        
        MAXI = max(MAXI , c);

        for(int k = 0 ; k < R.size() ; k++)
        {
            a = i+R[k].first;
            b = j+R[k].second;
            if(s[a][b] == '.' || vis[a][b] == 1)continue;
            vis[a][b] = 1;
            if(s[a][b] == s[i][j]){ q.push({-c,a*maxn+b});}
            else {q.push({-(c+1),a*maxn+b});}
        }
    }

    cout << MAXI << '\n';


    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:52:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int k = 0 ; k < R.size() ; k++)
      |                         ~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3164 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 16 ms 3284 KB Output is correct
5 Correct 3 ms 1884 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 4 ms 1624 KB Output is correct
11 Correct 5 ms 1372 KB Output is correct
12 Correct 11 ms 2060 KB Output is correct
13 Correct 3 ms 1880 KB Output is correct
14 Correct 3 ms 1884 KB Output is correct
15 Correct 21 ms 3128 KB Output is correct
16 Correct 29 ms 3164 KB Output is correct
17 Correct 13 ms 3032 KB Output is correct
18 Correct 18 ms 3240 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15452 KB Output is correct
2 Correct 85 ms 10156 KB Output is correct
3 Correct 242 ms 63336 KB Output is correct
4 Correct 108 ms 19024 KB Output is correct
5 Correct 137 ms 38992 KB Output is correct
6 Execution timed out 2048 ms 79792 KB Time limit exceeded
7 Correct 7 ms 16220 KB Output is correct
8 Correct 6 ms 15452 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 10 ms 15820 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 79 ms 10076 KB Output is correct
14 Correct 43 ms 6744 KB Output is correct
15 Correct 12 ms 7260 KB Output is correct
16 Correct 40 ms 3952 KB Output is correct
17 Correct 207 ms 20512 KB Output is correct
18 Correct 46 ms 20048 KB Output is correct
19 Correct 86 ms 19056 KB Output is correct
20 Correct 63 ms 17616 KB Output is correct
21 Correct 147 ms 40020 KB Output is correct
22 Correct 129 ms 38844 KB Output is correct
23 Correct 402 ms 33104 KB Output is correct
24 Correct 105 ms 39388 KB Output is correct
25 Correct 225 ms 63572 KB Output is correct
26 Correct 977 ms 50512 KB Output is correct
27 Correct 1668 ms 65396 KB Output is correct
28 Execution timed out 2009 ms 79804 KB Time limit exceeded
29 Execution timed out 2058 ms 71464 KB Time limit exceeded
30 Execution timed out 2003 ms 70324 KB Time limit exceeded
31 Correct 1330 ms 43776 KB Output is correct
32 Correct 1227 ms 64364 KB Output is correct