Submission #1233249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233249		thaocherry	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	834 ms	324544 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll H, W;
vector<ll> X{0,0,1,-1}, Y{1,-1,0,0};
const ll lim = 4e3 + 10;
char g[lim][lim], check[lim][lim];
struct abc{
    ll d,x,y;
};
bool cmp(abc a, abc b)
{
    if(a.d != b.d) return a.d > b.d;
    if(a.x != b.x) return a.x > b.x;
    return a.y > b.y;
}
set<abc, decltype(&cmp)> s(&cmp);
deque<abc> pq;
void init()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
}
void dj()
{
    ll ans = 1;
    pq.push_front({1,1,1});

    for(;pq.size();)
    {
        abc t = pq.front();
        pq.pop_front();
        ans = max(ans, t.d);
        if(check[t.x][t.y]) continue;
        check[t.x][t.y] = 1;
        for(ll i = 0; i < 4; i++)
        {
            ll vtX = t.x + X[i];
            ll vtY = t.y + Y[i];
            if(vtX <= 0 || vtX > H || vtY <= 0 || vtY > W || g[vtX][vtY] == '.' || check[vtX][vtY]) continue;
            if(g[vtX][vtY] != g[t.x][t.y]) pq.push_back({t.d + 1, vtX, vtY});
            else pq.push_front({t.d, vtX, vtY});
        }
    }
    cout << ans;
}
int main()
{
    init();
    cin >> H >> W;
    for(ll i = 1; i <= H; i++)
        for(ll j = 1; j <= W; j++) cin >> g[i][j];
    dj();

}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70