oj.uz

Submission #1091844

# Submission time Handle Problem Language Result Execution time Memory
1091844 2024-09-22T10:29:22 Z Jakub_Wozniak Tracks in the Snow (BOI13_tracks) C++14
93.4375 / 100
 2000 ms 76260 KB 
#include <bits/stdc++.h>
#include <stdio.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);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 0 ; i <= M+1 ; i++)SA.push_back( '.');
    s[0] = SA;
    s[N+1] = SA;


    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-i*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:58: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]
   58 |         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 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 16 ms 3160 KB Output is correct
5 Correct 3 ms 1984 KB Output is correct
6 Correct 1 ms 588 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 856 KB Output is correct
10 Correct 3 ms 1628 KB Output is correct
11 Correct 4 ms 1608 KB Output is correct
12 Correct 9 ms 1852 KB Output is correct
13 Correct 3 ms 1884 KB Output is correct
14 Correct 3 ms 1884 KB Output is correct
15 Correct 20 ms 3360 KB Output is correct
16 Correct 27 ms 3164 KB Output is correct
17 Correct 14 ms 3164 KB Output is correct
18 Correct 20 ms 3164 KB Output is correct

Subtask #2
63.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15448 KB Output is correct
2 Correct 71 ms 10132 KB Output is correct
3 Correct 223 ms 59624 KB Output is correct
4 Correct 79 ms 18484 KB Output is correct
5 Correct 127 ms 36944 KB Output is correct
6 Execution timed out 2005 ms 76260 KB Time limit exceeded
7 Correct 6 ms 16220 KB Output is correct
8 Correct 6 ms 15444 KB Output is correct
9 Correct 3 ms 860 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 72 ms 10132 KB Output is correct
14 Correct 42 ms 6744 KB Output is correct
15 Correct 13 ms 7256 KB Output is correct
16 Correct 41 ms 3932 KB Output is correct
17 Correct 213 ms 19800 KB Output is correct
18 Correct 53 ms 19800 KB Output is correct
19 Correct 80 ms 18488 KB Output is correct
20 Correct 56 ms 16984 KB Output is correct
21 Correct 134 ms 38224 KB Output is correct
22 Correct 123 ms 36888 KB Output is correct
23 Correct 406 ms 31764 KB Output is correct
24 Correct 108 ms 37620 KB Output is correct
25 Correct 206 ms 59728 KB Output is correct
26 Correct 951 ms 44628 KB Output is correct
27 Correct 1621 ms 58020 KB Output is correct
28 Execution timed out 2067 ms 72372 KB Time limit exceeded
29 Execution timed out 2029 ms 64048 KB Time limit exceeded
30 Correct 1956 ms 62960 KB Output is correct
31 Correct 1308 ms 33748 KB Output is correct
32 Correct 1242 ms 48724 KB Output is correct