oj.uz

Submission #920108

# Submission time Handle Problem Language Result Execution time Memory
920108 2024-02-02T04:33:02 Z thienbao1602 Tracks in the Snow (BOI13_tracks) C++17
31.7708 / 100
 2000 ms 777108 KB 
#include    <bits/stdc++.h>
#define SKY
#define ll long long
#define ld long double
#define MASK(x) (1LL << x)
#define sz(x) (int)x.size()
#define ii pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define set0(d) memset(d, 0, sizeof(d))
using namespace std;

const int LOG = 20;
const int base = 311;
const ll inf = 1e18;
const int block = 400;
const ll MOD = 1e9 + 7;
const int mxN = 1e6 + 66;
const int mxN2D = 4e3 + 55;
const int x[] = {0, 1, 0, -1};
const int y[] = {1, 0, -1, 0};

int H, W;
char grid[mxN2D][mxN2D];

bool safe(int x, int y)
{
    return (x >= 0 && x < H && y >= 0 && y < W && grid[x][y] != '.');
}

void solve()
{
    cin >> H >> W;
    for (int r=0; r<H; r++)
    {
        for(int c=0; c<W; c++)
        {
            cin >> grid[r][c];
        }
    }

    vector<vector<int>> depth(H, vector<int>(W, 0));
    queue<ii> pq;
    depth[0][0] = 1;
    pq.push(mp(0, 0));

  	int ans = 1;
    while(!pq.empty())
    {
        ii cell = pq.front();
        int u = cell.fi;
        int v = cell.se;

      	ans = max(ans, depth[u][v]);
        for (int i=0; i<4; i++)
        {
            int ux = u + x[i];
            int vx = v + y[i];

            if (safe(ux, vx))
            {
                if (depth[ux][vx] == 0 || depth[ux][vx] > depth[u][v])
                {
                    depth[ux][vx] = depth[u][v] + (grid[ux][vx] != grid[u][v]);
                    pq.push(mp(ux, vx));
                }
            }
        }
        pq.pop();
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    #ifdef SKY
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    #endif //SKY
    solve();
    return 0;
}

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 264696 KB Time limit exceeded
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 1 ms 2652 KB Output isn't correct
4 Incorrect 37 ms 3672 KB Output isn't correct
5 Incorrect 13 ms 2908 KB Output isn't correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 1 ms 2652 KB Output isn't correct
8 Incorrect 2 ms 2652 KB Output isn't correct
9 Incorrect 1 ms 2648 KB Output isn't correct
10 Incorrect 152 ms 16008 KB Output isn't correct
11 Incorrect 6 ms 2908 KB Output isn't correct
12 Execution timed out 2052 ms 250660 KB Time limit exceeded
13 Incorrect 14 ms 2908 KB Output isn't correct
14 Incorrect 14 ms 2904 KB Output isn't correct
15 Execution timed out 2045 ms 153428 KB Time limit exceeded
16 Execution timed out 2041 ms 242224 KB Time limit exceeded
17 Execution timed out 2040 ms 208536 KB Time limit exceeded
18 Incorrect 39 ms 3676 KB Output isn't correct

Subtask #2
28.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15960 KB Output is correct
2 Execution timed out 2069 ms 291764 KB Time limit exceeded
3 Execution timed out 2076 ms 251444 KB Time limit exceeded
4 Execution timed out 2050 ms 162932 KB Time limit exceeded
5 Correct 244 ms 52892 KB Output is correct
6 Execution timed out 2060 ms 638140 KB Time limit exceeded
7 Correct 4 ms 16472 KB Output is correct
8 Correct 4 ms 15708 KB Output is correct
9 Execution timed out 2055 ms 418604 KB Time limit exceeded
10 Correct 1 ms 604 KB Output is correct
11 Correct 4 ms 16220 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Execution timed out 2047 ms 290468 KB Time limit exceeded
14 Execution timed out 2096 ms 72748 KB Time limit exceeded
15 Correct 22 ms 8540 KB Output is correct
16 Execution timed out 2037 ms 172992 KB Time limit exceeded
17 Execution timed out 2043 ms 129552 KB Time limit exceeded
18 Correct 95 ms 24568 KB Output is correct
19 Execution timed out 2060 ms 160972 KB Time limit exceeded
20 Execution timed out 2077 ms 608240 KB Time limit exceeded
21 Execution timed out 2075 ms 577032 KB Time limit exceeded
22 Correct 207 ms 48208 KB Output is correct
23 Execution timed out 2096 ms 108932 KB Time limit exceeded
24 Correct 180 ms 48724 KB Output is correct
25 Correct 547 ms 79108 KB Output is correct
26 Correct 654 ms 63120 KB Output is correct
27 Incorrect 950 ms 79156 KB Output isn't correct
28 Execution timed out 2063 ms 650084 KB Time limit exceeded
29 Execution timed out 2124 ms 777108 KB Time limit exceeded
30 Execution timed out 2045 ms 269456 KB Time limit exceeded
31 Execution timed out 2051 ms 474540 KB Time limit exceeded
32 Execution timed out 2037 ms 88632 KB Time limit exceeded