oj.uz

Submission #920105

# Submission time Handle Problem Language Result Execution time Memory
920105 2024-02-02T04:31:00 Z thienbao1602 Tracks in the Snow (BOI13_tracks) C++17
52.2917 / 100
 2000 ms 810436 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));

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

        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();
    }

    int ans = 1;
    for(int r=0; r<H; r++)
    {
        for(int c=0; c<W; c++)
        {
            ans = max(ans, depth[r][c]);
        }
    }
    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
21.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2066 ms 310884 KB Time limit exceeded
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 2904 KB Output is correct
4 Correct 39 ms 3676 KB Output is correct
5 Correct 13 ms 3056 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 2 ms 2648 KB Output is correct
9 Correct 2 ms 2648 KB Output is correct
10 Correct 141 ms 15948 KB Output is correct
11 Correct 5 ms 2648 KB Output is correct
12 Execution timed out 2057 ms 250796 KB Time limit exceeded
13 Correct 13 ms 2904 KB Output is correct
14 Correct 13 ms 2908 KB Output is correct
15 Execution timed out 2054 ms 152780 KB Time limit exceeded
16 Execution timed out 2058 ms 294664 KB Time limit exceeded
17 Execution timed out 2051 ms 240128 KB Time limit exceeded
18 Correct 34 ms 3416 KB Output is correct

Subtask #2
30.625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15708 KB Output is correct
2 Execution timed out 2057 ms 289552 KB Time limit exceeded
3 Execution timed out 2036 ms 243888 KB Time limit exceeded
4 Execution timed out 2055 ms 161672 KB Time limit exceeded
5 Correct 210 ms 48208 KB Output is correct
6 Execution timed out 2096 ms 679176 KB Time limit exceeded
7 Correct 5 ms 16472 KB Output is correct
8 Correct 4 ms 15960 KB Output is correct
9 Execution timed out 2090 ms 420672 KB Time limit exceeded
10 Correct 1 ms 604 KB Output is correct
11 Correct 4 ms 16216 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Execution timed out 2054 ms 291160 KB Time limit exceeded
14 Execution timed out 2032 ms 73608 KB Time limit exceeded
15 Correct 26 ms 9304 KB Output is correct
16 Execution timed out 2047 ms 173788 KB Time limit exceeded
17 Execution timed out 2016 ms 131928 KB Time limit exceeded
18 Correct 100 ms 26704 KB Output is correct
19 Execution timed out 2043 ms 164672 KB Time limit exceeded
20 Execution timed out 2070 ms 611720 KB Time limit exceeded
21 Execution timed out 2062 ms 610944 KB Time limit exceeded
22 Correct 220 ms 52892 KB Output is correct
23 Execution timed out 2050 ms 133984 KB Time limit exceeded
24 Correct 192 ms 53232 KB Output is correct
25 Correct 603 ms 87140 KB Output is correct
26 Correct 689 ms 69200 KB Output is correct
27 Correct 952 ms 87376 KB Output is correct
28 Execution timed out 2050 ms 689260 KB Time limit exceeded
29 Execution timed out 2051 ms 810436 KB Time limit exceeded
30 Execution timed out 2035 ms 269776 KB Time limit exceeded
31 Execution timed out 2056 ms 489852 KB Time limit exceeded
32 Execution timed out 2019 ms 88384 KB Time limit exceeded