oj.uz

Submission #895547

# Submission time Handle Problem Language Result Execution time Memory
895547 2023-12-30T08:47:21 Z 123456321 Tracks in the Snow (BOI13_tracks) C++17
19.7917 / 100
 2000 ms 262428 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;
    int ans = 0;
    while(!q.empty())
    {
        auto curr = q.front();
        q.pop_front();
        int x = curr.first;
        int y = curr.second;
        if(vis[x][y])continue;
        ans = max(ans,dist[x][y]);
        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});
                }
            }
        }
    }
    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 30 ms 3848 KB Output isn't correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Correct 16 ms 2648 KB Output is correct
5 Incorrect 11 ms 1636 KB Output isn't correct
6 Incorrect 0 ms 856 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 348 KB Output isn't correct
10 Incorrect 7 ms 1368 KB Output isn't correct
11 Correct 5 ms 1112 KB Output is correct
12 Incorrect 11 ms 1628 KB Output isn't correct
13 Incorrect 9 ms 1628 KB Output isn't correct
14 Incorrect 9 ms 1628 KB Output isn't correct
15 Incorrect 29 ms 4300 KB Output isn't correct
16 Incorrect 30 ms 3872 KB Output isn't correct
17 Incorrect 28 ms 3804 KB Output isn't correct
18 Correct 19 ms 2652 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1372 KB Output isn't correct
2 Incorrect 198 ms 24820 KB Output isn't correct
3 Incorrect 1601 ms 262428 KB Output isn't correct
4 Incorrect 428 ms 52448 KB Output isn't correct
5 Incorrect 807 ms 154816 KB Output isn't correct
6 Correct 1859 ms 232560 KB Output is correct
7 Incorrect 6 ms 1628 KB Output isn't correct
8 Incorrect 6 ms 1372 KB Output isn't correct
9 Incorrect 6 ms 1256 KB Output isn't correct
10 Incorrect 3 ms 860 KB Output isn't correct
11 Incorrect 6 ms 1580 KB Output isn't correct
12 Incorrect 2 ms 604 KB Output isn't correct
13 Incorrect 161 ms 24904 KB Output isn't correct
14 Incorrect 90 ms 14956 KB Output isn't correct
15 Incorrect 120 ms 16464 KB Output isn't correct
16 Incorrect 68 ms 10292 KB Output isn't correct
17 Incorrect 413 ms 65680 KB Output isn't correct
18 Incorrect 548 ms 64280 KB Output isn't correct
19 Incorrect 399 ms 52420 KB Output isn't correct
20 Incorrect 331 ms 56960 KB Output isn't correct
21 Incorrect 911 ms 149280 KB Output isn't correct
22 Incorrect 801 ms 155112 KB Output isn't correct
23 Incorrect 801 ms 120012 KB Output isn't correct
24 Incorrect 860 ms 144328 KB Output isn't correct
25 Execution timed out 2060 ms 256612 KB Time limit exceeded
26 Correct 1126 ms 208056 KB Output is correct
27 Correct 1500 ms 245608 KB Output is correct
28 Correct 1802 ms 232520 KB Output is correct
29 Correct 1834 ms 230980 KB Output is correct
30 Correct 1649 ms 232304 KB Output is correct
31 Incorrect 1399 ms 133672 KB Output isn't correct
32 Incorrect 1518 ms 234560 KB Output isn't correct