oj.uz

Submission #1091830

# Submission time Handle Problem Language Result Execution time Memory
1091830 2024-09-22T10:12:24 Z Jakub_Wozniak Tracks in the Snow (BOI13_tracks) C++14
93.4375 / 100
 2000 ms 79820 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4009;
typedef long long ll;
int N , M;
string s[maxn];
string SA;
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 >> SA;
        s[i] = '.';
        s[i] += SA;
        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])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:54: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]
   54 |         for(int k = 0 ; k < R.size() ; k++)
      |                         ~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3160 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 16 ms 3184 KB Output is correct
5 Correct 3 ms 1884 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 4 ms 1628 KB Output is correct
11 Correct 4 ms 1556 KB Output is correct
12 Correct 10 ms 1880 KB Output is correct
13 Correct 4 ms 1884 KB Output is correct
14 Correct 3 ms 1980 KB Output is correct
15 Correct 20 ms 3356 KB Output is correct
16 Correct 27 ms 3164 KB Output is correct
17 Correct 14 ms 3164 KB Output is correct
18 Correct 17 ms 3164 KB Output is correct

Subtask #2
63.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15448 KB Output is correct
2 Correct 78 ms 10072 KB Output is correct
3 Correct 241 ms 63060 KB Output is correct
4 Correct 87 ms 18768 KB Output is correct
5 Correct 135 ms 38740 KB Output is correct
6 Execution timed out 2021 ms 79788 KB Time limit exceeded
7 Correct 8 ms 16220 KB Output is correct
8 Correct 7 ms 15452 KB Output is correct
9 Correct 3 ms 908 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 7 ms 15856 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 75 ms 10076 KB Output is correct
14 Correct 41 ms 6748 KB Output is correct
15 Correct 13 ms 7256 KB Output is correct
16 Correct 37 ms 3932 KB Output is correct
17 Correct 212 ms 20304 KB Output is correct
18 Correct 52 ms 20052 KB Output is correct
19 Correct 90 ms 19196 KB Output is correct
20 Correct 65 ms 17600 KB Output is correct
21 Correct 144 ms 40228 KB Output is correct
22 Correct 130 ms 38736 KB Output is correct
23 Correct 428 ms 33104 KB Output is correct
24 Correct 113 ms 39376 KB Output is correct
25 Correct 235 ms 63320 KB Output is correct
26 Correct 965 ms 50456 KB Output is correct
27 Correct 1614 ms 65408 KB Output is correct
28 Execution timed out 2063 ms 79820 KB Time limit exceeded
29 Execution timed out 2013 ms 71684 KB Time limit exceeded
30 Correct 1929 ms 70276 KB Output is correct
31 Correct 1300 ms 43856 KB Output is correct
32 Correct 1301 ms 64456 KB Output is correct