oj.uz

Submission #895545

# Submission time Handle Problem Language Result Execution time Memory
895545 2023-12-30T08:42:18 Z 123456321 Tracks in the Snow (BOI13_tracks) C++17
19.7917 / 100
 2000 ms 262412 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});
    dist[0][0] = 1;
    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;
            ans = max(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
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 3676 KB Output isn't correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Correct 16 ms 2652 KB Output is correct
5 Incorrect 9 ms 1628 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 1 ms 344 KB Output isn't correct
10 Incorrect 7 ms 1368 KB Output isn't correct
11 Correct 5 ms 860 KB Output is correct
12 Incorrect 12 ms 1628 KB Output isn't correct
13 Incorrect 10 ms 1880 KB Output isn't correct
14 Incorrect 11 ms 1476 KB Output isn't correct
15 Incorrect 33 ms 4188 KB Output isn't correct
16 Incorrect 30 ms 3672 KB Output isn't correct
17 Incorrect 28 ms 3808 KB Output isn't correct
18 Correct 17 ms 2648 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1372 KB Output isn't correct
2 Incorrect 191 ms 24760 KB Output isn't correct
3 Incorrect 1564 ms 262412 KB Output isn't correct
4 Incorrect 401 ms 52560 KB Output isn't correct
5 Incorrect 822 ms 154928 KB Output isn't correct
6 Correct 1872 ms 232716 KB Output is correct
7 Incorrect 6 ms 1628 KB Output isn't correct
8 Incorrect 6 ms 1620 KB Output isn't correct
9 Incorrect 6 ms 1356 KB Output isn't correct
10 Incorrect 3 ms 860 KB Output isn't correct
11 Incorrect 6 ms 1628 KB Output isn't correct
12 Incorrect 3 ms 604 KB Output isn't correct
13 Incorrect 160 ms 24944 KB Output isn't correct
14 Incorrect 95 ms 14932 KB Output isn't correct
15 Incorrect 122 ms 16468 KB Output isn't correct
16 Incorrect 67 ms 10292 KB Output isn't correct
17 Incorrect 423 ms 65808 KB Output isn't correct
18 Incorrect 524 ms 64256 KB Output isn't correct
19 Incorrect 411 ms 52404 KB Output isn't correct
20 Incorrect 389 ms 56928 KB Output isn't correct
21 Incorrect 893 ms 149164 KB Output isn't correct
22 Incorrect 796 ms 154836 KB Output isn't correct
23 Incorrect 775 ms 120056 KB Output isn't correct
24 Incorrect 848 ms 144492 KB Output isn't correct
25 Execution timed out 2078 ms 256576 KB Time limit exceeded
26 Correct 1159 ms 207964 KB Output is correct
27 Correct 1523 ms 245716 KB Output is correct
28 Correct 1945 ms 232444 KB Output is correct
29 Correct 1803 ms 231024 KB Output is correct
30 Correct 1684 ms 232428 KB Output is correct
31 Incorrect 1454 ms 133972 KB Output isn't correct
32 Incorrect 1552 ms 234248 KB Output isn't correct