oj.uz

Submission #895544

# Submission time Handle Problem Language Result Execution time Memory
895544 2023-12-30T08:36:27 Z 123456321 Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 303 ms 234580 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1000000007;
int n,m;
#define pb push_back
#define mp make_pair
vector<vector<pair<int,int>>> adj;


void solve()
{
    cin >> n >>m ;
    vector<string> snow(n);
    for(int i = 0;i<n;i++)cin >> snow[i];
    deque<pair<int,int>> q;
    vector<vector<int>> vis(n,vector<int>(m,0));
    vector<vector<int>> dist(n,vector<int>(m,1e9));
    vector<vector<int>> parent(n,vector<int>(m,-1));    
    vector<vector<int>> dir = {{1,0},{-1,0},{0,1},{0,-1}};
    q.push_back({0,0});
    while(!q.empty())
    {
        auto curr = q.front();
        q.pop_front();
        int x = curr.first;
        int y = curr.second;
        if(vis[x][y])continue;
        vis[x][y] = 1;
        for(auto d : dir)
        {
            int nx = x + d[0];
            int ny = y + d[1];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
            if(snow[nx][ny] == snow[x][y])
            {
                if(dist[nx][ny] > dist[x][y])
                {
                    dist[nx][ny] = dist[x][y];
                    parent[nx][ny] = parent[x][y];
                    q.push_front({nx,ny});
                }
            }
            else
            {
                if(dist[nx][ny] > dist[x][y] + 1)
                {
                    dist[nx][ny] = dist[x][y] + 1;
                    parent[nx][ny] = parent[x][y];
                    q.push_back({nx,ny});
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<m;j++)
        {
            if(dist[i][j] == 1e9)continue;
            if(snow[i][j] == '1')continue;
            if(dist[i][j] > ans)
            {
                ans = dist[i][j];
            }
        }
    }
    cout << ans << "\n";
    return;
}
int main()
{
    int tests = 1;
    //cin >> tests;
    int i = 1;
    while (i <= tests)
    {
        //cout << "Case #"<< i<< ": ";
        solve();
        if(i!=tests)cout << "\n";
        i++;
    }
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3932 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 3 ms 2652 KB Output isn't correct
5 Incorrect 2 ms 1628 KB Output isn't correct
6 Incorrect 0 ms 432 KB Output isn't correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Incorrect 1 ms 604 KB Output isn't correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Incorrect 2 ms 1368 KB Output isn't correct
11 Incorrect 1 ms 1112 KB Output isn't correct
12 Incorrect 3 ms 1628 KB Output isn't correct
13 Incorrect 2 ms 1628 KB Output isn't correct
14 Incorrect 2 ms 1628 KB Output isn't correct
15 Incorrect 5 ms 4140 KB Output isn't correct
16 Incorrect 5 ms 4032 KB Output isn't correct
17 Incorrect 5 ms 3932 KB Output isn't correct
18 Incorrect 3 ms 2492 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1372 KB Output isn't correct
2 Incorrect 31 ms 22572 KB Output isn't correct
3 Incorrect 301 ms 234536 KB Output isn't correct
4 Incorrect 72 ms 55380 KB Output isn't correct
5 Incorrect 162 ms 126548 KB Output isn't correct
6 Incorrect 301 ms 234544 KB Output isn't correct
7 Incorrect 2 ms 1628 KB Output isn't correct
8 Incorrect 2 ms 1468 KB Output isn't correct
9 Incorrect 1 ms 1116 KB Output isn't correct
10 Incorrect 1 ms 860 KB Output isn't correct
11 Incorrect 2 ms 1468 KB Output isn't correct
12 Incorrect 1 ms 604 KB Output isn't correct
13 Incorrect 29 ms 22712 KB Output isn't correct
14 Incorrect 17 ms 13660 KB Output isn't correct
15 Incorrect 19 ms 14936 KB Output isn't correct
16 Incorrect 12 ms 9232 KB Output isn't correct
17 Incorrect 75 ms 59736 KB Output isn't correct
18 Incorrect 74 ms 59112 KB Output isn't correct
19 Incorrect 69 ms 55504 KB Output isn't correct
20 Incorrect 63 ms 51024 KB Output isn't correct
21 Incorrect 168 ms 130896 KB Output isn't correct
22 Incorrect 162 ms 126544 KB Output isn't correct
23 Incorrect 143 ms 108624 KB Output isn't correct
24 Incorrect 164 ms 128068 KB Output isn't correct
25 Incorrect 300 ms 234320 KB Output isn't correct
26 Incorrect 222 ms 169296 KB Output isn't correct
27 Incorrect 301 ms 234580 KB Output isn't correct
28 Incorrect 293 ms 234320 KB Output isn't correct
29 Incorrect 303 ms 234320 KB Output isn't correct
30 Incorrect 294 ms 229020 KB Output isn't correct
31 Incorrect 189 ms 143184 KB Output isn't correct
32 Incorrect 301 ms 234296 KB Output isn't correct