oj.uz

Submission #339092

# Submission time Handle Problem Language Result Execution time Memory
339092 2020-12-24T15:14:35 Z Magi Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 648 ms 174204 KB 
#include <iostream>
#include <deque>
#define NMAX 4000

using namespace std;

int n, m, viz[NMAX+10][NMAX+10], cost[NMAX+10][NMAX+10], ans;
char v[NMAX+10][NMAX+10];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
deque <pair <int, int> > dq;

void bfs()
{   viz[1][1] = 1;
    while(!dq.empty())
        {   pair <int, int> a = dq.front();
            dq.pop_front();
            for(int t=0; t<4; t++)
                {   pair <int, int> vec = {dx[t] + a.first, dy[t] + a.second};
                    if(vec.first && vec.first <= n && vec.second && vec.second <= m
                       && !viz[vec.first][vec.second])
                        {   viz[vec.first][vec.second] = 1;
                            if(v[a.first][a.second] == v[vec.first][vec.second])
                                {   dq.push_front(vec);
                                    cost[vec.first][vec.second] = cost[a.first][a.second];
                                }
                            else
                                {   dq.push_back(vec);
                                    cost[vec.first][vec.second] = cost[a.first][a.second] + 1;
                                }
                        }
                }
        }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        {   string s;
            cin >> s;
            for(int j=0; j<m; j++)
                {   v[i][j+1] = s[j];
                    if(s[j] == '.') viz[i][j+1] = 1;
                }
        }
    dq.push_front({1, 1});
    bfs();
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            ans = max(ans, cost[i][j]);
    cout << ans + 1<< '\n';
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8172 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 10 ms 7660 KB Output is correct
5 Correct 4 ms 4460 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 1004 KB Output is correct
8 Correct 1 ms 1132 KB Output is correct
9 Correct 1 ms 1644 KB Output is correct
10 Correct 4 ms 3692 KB Output is correct
11 Correct 3 ms 3180 KB Output is correct
12 Correct 6 ms 4588 KB Output is correct
13 Correct 4 ms 4460 KB Output is correct
14 Correct 4 ms 4460 KB Output is correct
15 Correct 13 ms 8044 KB Output is correct
16 Correct 15 ms 8204 KB Output is correct
17 Correct 11 ms 7916 KB Output is correct
18 Correct 10 ms 7660 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 46444 KB Output is correct
2 Correct 49 ms 24832 KB Output is correct
3 Correct 228 ms 120556 KB Output is correct
4 Correct 105 ms 51308 KB Output is correct
5 Correct 165 ms 91756 KB Output is correct
6 Correct 648 ms 156228 KB Output is correct
7 Correct 28 ms 48620 KB Output is correct
8 Correct 26 ms 46444 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 27 ms 47596 KB Output is correct
12 Correct 2 ms 2284 KB Output is correct
13 Correct 49 ms 24812 KB Output is correct
14 Correct 29 ms 16876 KB Output is correct
15 Correct 32 ms 20204 KB Output is correct
16 Correct 20 ms 9324 KB Output is correct
17 Correct 122 ms 48748 KB Output is correct
18 Correct 118 ms 55532 KB Output is correct
19 Correct 92 ms 51436 KB Output is correct
20 Correct 63 ms 42732 KB Output is correct
21 Correct 149 ms 92268 KB Output is correct
22 Correct 165 ms 91756 KB Output is correct
23 Correct 226 ms 75432 KB Output is correct
24 Correct 150 ms 89196 KB Output is correct
25 Correct 525 ms 141804 KB Output is correct
26 Correct 365 ms 174204 KB Output is correct
27 Correct 504 ms 171040 KB Output is correct
28 Correct 646 ms 156484 KB Output is correct
29 Correct 642 ms 152524 KB Output is correct
30 Correct 588 ms 158832 KB Output is correct
31 Correct 587 ms 114028 KB Output is correct
32 Correct 486 ms 161320 KB Output is correct