oj.uz

Submission #498919

# Submission time Handle Problem Language Result Execution time Memory
498919 2021-12-26T17:11:59 Z BBart888 Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 984 ms 132928 KB 
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include<stack>
#include <set>



using namespace std;
using ll = long long;

const int INF = 1e9;
const int MAXN = 4e3+111;
const int MOD = 1e9 + 7;
const int MAXS = 250*1000+123;



int n, m;
char t[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dist[MAXN][MAXN];
int ans = 0;
pair<int, int> dd[]{ {0,1},{0,-1},{1,0},{-1,0} };


bool isIn(int i, int j)
{
    if (i < n && j < n && i >= 0 && j >= 0 && t[i][j] != '.')
        return true;
    else
        return false;
}

void bfs(int i, int j)
{
    deque<pair<int,int>> q;
    q.push_back({ i,j });
    dist[i][j] = 1;

    while (!q.empty())
    {
        pair<int,int> s = q.front();
        q.pop_front();
        ans = max(ans, dist[s.first][s.second]);
        for (pair<int, int> d : dd)
        {
            int newI = s.first + d.first;
            int newJ = s.second + d.second;
            
            if (isIn(newI, newJ) && dist[newI][newJ] == 0)
            {
                int w = (t[i][j] != t[newI][newJ]);
               
                dist[newI][newJ] = dist[i][j] + w;
                if (w == 1)
                    q.push_back({ newI,newJ });
                else
                    q.push_front({ newI,newJ });
            }

        }

    }





}


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


    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> t[i][j];



    bfs(0, 0);

    cout << ans << endl;











    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 5444 KB Output isn't correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Incorrect 1 ms 712 KB Output isn't correct
4 Incorrect 12 ms 5444 KB Output isn't correct
5 Incorrect 4 ms 2952 KB Output isn't correct
6 Incorrect 1 ms 460 KB Output isn't correct
7 Incorrect 1 ms 716 KB Output isn't correct
8 Incorrect 1 ms 844 KB Output isn't correct
9 Incorrect 1 ms 1100 KB Output isn't correct
10 Incorrect 3 ms 2516 KB Output isn't correct
11 Incorrect 3 ms 2196 KB Output isn't correct
12 Incorrect 5 ms 3016 KB Output isn't correct
13 Incorrect 4 ms 2892 KB Output isn't correct
14 Incorrect 4 ms 2884 KB Output isn't correct
15 Incorrect 12 ms 5256 KB Output isn't correct
16 Incorrect 14 ms 5388 KB Output isn't correct
17 Incorrect 13 ms 5188 KB Output isn't correct
18 Incorrect 15 ms 5424 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 527 ms 77184 KB Output isn't correct
2 Incorrect 62 ms 15136 KB Output isn't correct
3 Incorrect 385 ms 74480 KB Output isn't correct
4 Incorrect 102 ms 32060 KB Output isn't correct
5 Incorrect 258 ms 53888 KB Output isn't correct
6 Incorrect 941 ms 103336 KB Output isn't correct
7 Incorrect 621 ms 80824 KB Output isn't correct
8 Incorrect 604 ms 77160 KB Output isn't correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Incorrect 1 ms 344 KB Output isn't correct
11 Incorrect 561 ms 79376 KB Output isn't correct
12 Incorrect 2 ms 1612 KB Output isn't correct
13 Incorrect 51 ms 15196 KB Output isn't correct
14 Incorrect 29 ms 10404 KB Output isn't correct
15 Incorrect 35 ms 13156 KB Output isn't correct
16 Incorrect 12 ms 2888 KB Output isn't correct
17 Incorrect 134 ms 32376 KB Output isn't correct
18 Incorrect 118 ms 35836 KB Output isn't correct
19 Incorrect 131 ms 32044 KB Output isn't correct
20 Incorrect 51 ms 10936 KB Output isn't correct
21 Incorrect 230 ms 63332 KB Output isn't correct
22 Incorrect 249 ms 53824 KB Output isn't correct
23 Incorrect 233 ms 37724 KB Output isn't correct
24 Incorrect 231 ms 52416 KB Output isn't correct
25 Incorrect 522 ms 96420 KB Output isn't correct
26 Correct 644 ms 132928 KB Output is correct
27 Incorrect 759 ms 114984 KB Output isn't correct
28 Incorrect 984 ms 103144 KB Output isn't correct
29 Incorrect 914 ms 104080 KB Output isn't correct
30 Incorrect 801 ms 102256 KB Output isn't correct
31 Incorrect 499 ms 75120 KB Output isn't correct
32 Incorrect 756 ms 96460 KB Output isn't correct