Submission #920105

#	Time	Username	Problem	Language	Result	Execution time	Memory
920105		thienbao1602	Tracks in the Snow (BOI13_tracks)	C++17	52.29 / 100	2096 ms	810436 KiB

tracks

#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.666666666666668 / 30
• Subtask 2: 30.625 / 70