oj.uz

Submission #1091820

# Submission time Handle Problem Language Result Execution time Memory
1091820 2024-09-22T09:52:37 Z Jakub_Wozniak Tracks in the Snow (BOI13_tracks) C++14
86.875 / 100
 2000 ms 79800 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] += '&';
    for(int i = 0 ; i <= M+1 ; i++ )s[N+1] += '&';

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

    priority_queue <pair<int,int>> q;
    q.push({-1,1*maxn+1});
    int i , j;
    while(!q.empty())
    {
        c = -q.top().first; 
        i = q.top().second/maxn;
        j = q.top().second%maxn;
        q.pop();
        if(vis[i][j] == 1){continue;}
        vis[i][j] = 1;
        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] == '&' || s[a][b] == '.' || vis[a][b] == 1)continue;
            
            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:49: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]
   49 |         for(int k = 0 ; k < R.size() ; k++)
      |                         ~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3420 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 27 ms 3476 KB Output is correct
5 Correct 4 ms 1884 KB Output is correct
6 Correct 0 ms 600 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 7 ms 1612 KB Output is correct
12 Correct 17 ms 1884 KB Output is correct
13 Correct 3 ms 1880 KB Output is correct
14 Correct 4 ms 1876 KB Output is correct
15 Correct 35 ms 3416 KB Output is correct
16 Correct 50 ms 3476 KB Output is correct
17 Correct 18 ms 3164 KB Output is correct
18 Correct 28 ms 3436 KB Output is correct

Subtask #2
56.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15452 KB Output is correct
2 Correct 107 ms 10076 KB Output is correct
3 Correct 302 ms 63476 KB Output is correct
4 Correct 91 ms 19032 KB Output is correct
5 Correct 125 ms 38736 KB Output is correct
6 Execution timed out 2078 ms 79784 KB Time limit exceeded
7 Correct 7 ms 16220 KB Output is correct
8 Correct 6 ms 15520 KB Output is correct
9 Correct 5 ms 948 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 6 ms 15964 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 114 ms 10168 KB Output is correct
14 Correct 62 ms 6904 KB Output is correct
15 Correct 12 ms 7256 KB Output is correct
16 Correct 73 ms 4116 KB Output is correct
17 Correct 297 ms 20572 KB Output is correct
18 Correct 58 ms 20056 KB Output is correct
19 Correct 93 ms 19036 KB Output is correct
20 Correct 82 ms 17608 KB Output is correct
21 Correct 198 ms 40016 KB Output is correct
22 Correct 142 ms 38616 KB Output is correct
23 Correct 566 ms 33516 KB Output is correct
24 Correct 101 ms 39768 KB Output is correct
25 Correct 261 ms 63348 KB Output is correct
26 Correct 1351 ms 50260 KB Output is correct
27 Execution timed out 2009 ms 65492 KB Time limit exceeded
28 Execution timed out 2091 ms 79752 KB Time limit exceeded
29 Execution timed out 2009 ms 79800 KB Time limit exceeded
30 Execution timed out 2092 ms 78576 KB Time limit exceeded
31 Execution timed out 2009 ms 44236 KB Time limit exceeded
32 Correct 1916 ms 65344 KB Output is correct