Submission #710783

#	Time	Username	Problem	Language	Result	Execution time	Memory
710783		pls33	Tracks in the Snow (BOI13_tracks)	C++17	47.50 / 100	2094 ms	84176 KiB

tracks

// boi2013 day2 p2
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using f80 = long double;
#pragma endregion

using grid_t = vector<string>;

const vi16 dx = {1, -1, 0, 0};
const vi16 dy = {0, 0, 1, -1};

bool inside(p32 a, int row, int col)
{
    return a.first >= 0 && a.first < row &&
           a.second >= 0 && a.second < col;
}

// sauce: https://judge.yosupo.jp/submission/76471
template <uint32_t N>
struct Bitset
{
    using u64 = std::uint64_t;
    using u32 = std::uint32_t;
    using i32 = std::int32_t;

private:
    static constexpr u64 ONE = 1;
    static constexpr u64 ZERO = 0;
    static constexpr u64 ALL_MASK = ~ZERO;
    static constexpr u32 BITS = sizeof(u64) * CHAR_BIT;
    static constexpr u32 ALL = BITS - 1;
    static constexpr u32 CAPACITY = (N + BITS - 1) / BITS;
    static constexpr u32 REMAINING = N & ALL;
    static constexpr u64 CLEANUP_MASK = ~(ALL_MASK << REMAINING);
    u64 a[CAPACITY];
    /**
     * storage:
     * a[0] = bit_63,   ..., bit_0
     * a[1] = bit_127,  ..., bit_64
     * ...
     *
     * semantics of <<= and >>= : usual <<= and >>= semantics for u64
     */

    // NOTE: range violations are undefined behaviour and are unchecked
    struct reference
    {
    private:
        u32 pos;
        u64 *a;

    public:
        reference(u32 p, u64 *aa) : pos(p), a(aa) {}
        reference &operator=(bool x) noexcept
        {
            if (x)
                *a |= ONE << pos;
            else
                *a &= ~(ONE << pos);
            return *this;
        }
        reference &operator=(const reference &x) noexcept
        {
            if ((*x.a >> x.pos) & 1)
                *a |= ONE << pos;
            else
                *a &= ~(ONE << pos);
            return *this;
        }
        operator bool() const noexcept { return (*a >> pos) & 1; }
        bool operator~() const noexcept { return !((*a >> pos) & 1); }
        reference &flip() noexcept { *a ^= ONE << pos; }
    };

    inline void cleanup() noexcept { a[CAPACITY - 1] &= CLEANUP_MASK; }

public:
    constexpr Bitset() noexcept
    {
        static_assert(BITS == 64, "Won't work on this architecture");
        static_assert(N > 0, "Size of parameter should be a positive integer");
        reset();
    };

    constexpr Bitset(u64 x) noexcept : Bitset() { a[0] = x; };

    constexpr Bitset(const std::string &x) : Bitset()
    {
#ifdef DEBUG
        if (x.size() > N * BITS)
            throw std::out_of_range("String is too large to convert to Bitset");
#endif
        u32 cur_loc = 0;
        u32 bit = 0;
        for (const auto c : x)
        {
#ifdef DEBUG
            if (c != '0' && c != '1')
                throw std::invalid_argument(
                    "String should consist of only 0s and 1s");
#endif
            a[cur_loc] |= u64(c - '0') << (bit++);
            if (bit == BITS)
                bit = 0, ++cur_loc;
        }
    }

    constexpr Bitset(const Bitset &b)
    {
        std::copy(std::begin(b.a), std::end(b.a), std::begin(a));
    }

    bool operator==(const Bitset &b) const
    {
        return std::equal(std::begin(a), std::end(a), std::begin(b.a));
    }

    bool operator!=(const Bitset &b) const { return !(*this == b); }

    constexpr bool operator[](u32 pos) const
    {
#ifdef DEBUG
        assert(("Bitset index out of range, UB", pos >= 0 && pos < N));
#endif
        return (a[pos / BITS] >> (pos & ALL)) & 1;
    }

    reference operator[](u32 pos)
    {
#ifdef DEBUG
        assert(("Bitset index out of range, UB", pos >= 0 && pos < N));
#endif
        return reference(pos & ALL, a + pos / BITS);
    }

    std::string to_string() const
    {
        std::string s(N, '0');
        auto it = s.data() + N - 1;
        for (u32 i = 0; i < N; ++i)
            *(it--) += (a[i / BITS] >> (i & ALL)) & 1;
        return s;
    }

    u32 count() const noexcept
    {
        u32 ans = 0;
        for (u32 i = 0; i < CAPACITY; ++i)
            ans += __builtin_popcountll(a[i]);
        return ans;
    }

    u32 size() const noexcept { return N; }

#define IMPLEMENT(op)                             \
    Bitset &operator op(const Bitset &b) noexcept \
    {                                             \
        for (u32 i = 0; i < CAPACITY; ++i)        \
            a[i] op b.a[i];                       \
        return *this;                             \
    }
    IMPLEMENT(&=)
    IMPLEMENT(|=)
    IMPLEMENT(^=)
#undef IMPLEMENT
    Bitset &flip() noexcept
    {
        for (u32 i = 0; i < CAPACITY; ++i)
            a[i] = ~a[i];
        cleanup();
        return *this;
    }
    Bitset operator~() const noexcept { return Bitset(*this).flip(); }

    Bitset &operator<<=(u32 n) noexcept
    {
        if (n > N)
        {
            reset();
            return *this;
        }
        if (__builtin_expect(n != 0, 1))
        {
            const u32 loc = n / BITS;
            const u32 pos = n & ALL;
            if (pos == 0)
                for (u32 i = CAPACITY - 1; i != loc - 1; --i)
                    a[i] = a[i - loc];
            else
            {
                const u32 complement = BITS - pos;
                for (u32 i = CAPACITY - 1; i != loc - 1; --i)
                    a[i] = (a[i - loc] << pos) | (a[i - loc - 1] >> complement);
                a[loc] = a[0] << pos;
            }
            std::fill(std::begin(a), std::begin(a) + loc, 0);
            cleanup();
        }
        return *this;
    }

    // 01000 -> 00100
    Bitset &operator>>=(u32 n) noexcept
    {
        if (n > N)
        {
            reset();
            return *this;
        }
        if (__builtin_expect(n != 0, 1))
        {
            const u32 loc = n / BITS;
            const u32 pos = n & ALL;
            const u32 l = CAPACITY - 1 - loc;
            if (pos == 0)
                for (u32 i = 0; i <= l; ++i)
                    a[i] = a[i + loc];
            else
            {
                const u32 complement = BITS - pos;
                for (u32 i = 0; i < l; ++i)
                    a[i] = (a[i + loc] >> pos) | (a[i + loc + 1] << complement);
                a[l] = a[CAPACITY - 1] >> pos;
            }
            std::fill(std::begin(a) + l + 1, std::end(a), 0);
            cleanup();
        }
        return *this;
    }

    Bitset operator<<(u32 n) const noexcept { return Bitset(*this) <<= n; }
    Bitset operator>>(u32 n) const noexcept { return Bitset(*this) >>= n; }

    void reset() noexcept { std::fill(std::begin(a), std::end(a), 0); }

    void set() noexcept
    {
        std::fill(std::begin(a), std::end(a), ALL_MASK);
        cleanup();
    }

    // warning: these use ints and not u

    i32 find_first_set() const noexcept
    {
        for (i32 i = 0; i < (i32)CAPACITY; ++i)
        {
            u64 w = a[i];
            if (w)
                return i * BITS + __builtin_ctzll(w);
        }
        return N;
    }

    i32 find_first_unset() const noexcept
    {
        for (i32 i = 0; i < CAPACITY; ++i)
        {
            u64 w = ~a[i];
            if (w)
                return i * BITS + __builtin_ctzll(w);
        }
        return N;
    }

    i32 find_next_set(i32 i) const noexcept
    {
        ++i;
        if (i >= BITS * CAPACITY)
            return N;
        i32 loc = i / BITS;
        u64 w = a[loc] & (ALL_MASK << (i & ALL));
        if (w)
            return loc * BITS + __builtin_ctzll(w);
        for (++loc; loc < CAPACITY; ++loc)
        {
            w = a[loc];
            if (w)
                return loc * BITS + __builtin_ctzll(w);
        }
        return N;
    }

    i32 find_next_unset(i32 i) const noexcept
    {
        ++i;
        if (i >= BITS * CAPACITY)
            return N;
        i32 loc = i / BITS;
        u64 w = (~a[loc]) & (ALL_MASK << (i & ALL));
        if (w)
            return loc * BITS + __builtin_ctzll(w);
        for (++loc; loc < CAPACITY; ++loc)
        {
            w = ~a[loc];
            if (w)
                return loc * BITS + __builtin_ctzll(w);
        }
        return N;
    }

    i32 find_prev_set(i32 i) const noexcept
    {
        --i;
        if (i < 0)
            return -1;
        i32 loc = i / BITS;
        u64 w = a[loc] & (ALL_MASK >> (ALL ^ (i & ALL)));
        if (w)
            return loc * BITS + (ALL ^ __builtin_clzll(w));
        for (--loc; loc >= 0; --loc)
        {
            w = a[loc];
            if (w)
                return loc * BITS + (ALL ^ __builtin_clzll(w));
        }
        return -1;
    }

    i32 find_prev_unset(i32 i) const noexcept
    {
        --i;
        if (i < 0)
            return -1;
        i32 loc = i / BITS;
        u64 w = (~a[loc]) & (ALL_MASK >> (ALL ^ (i & ALL)));
        if (w)
            return loc * BITS + (ALL ^ __builtin_clzll(w));
        for (--loc; loc >= 0; --loc)
        {
            w = ~a[loc];
            if (w)
                return loc * BITS + (ALL ^ __builtin_clzll(w));
        }
        return -1;
    }

    i32 find_next_set(i32 i, i32 max_iter) const noexcept
    {
        ++i;
        if (i >= BITS * CAPACITY)
            return N;
        i32 loc = i / BITS;
        u64 w = a[loc] & (ALL_MASK << (i & ALL));
        if (w)
            return loc * BITS + __builtin_ctzll(w);
        int iter = 0;
        for (++loc; loc < CAPACITY && iter < max_iter; ++loc, ++iter)
        {
            w = a[loc];
            if (w)
                return loc * BITS + __builtin_ctzll(w);
        }
        return N;
    }

    i32 find_next_unset(i32 i, i32 max_iter) const noexcept
    {
        ++i;
        if (i >= BITS * CAPACITY)
            return N;
        i32 loc = i / BITS;
        u64 w = (~a[loc]) & (ALL_MASK << (i & ALL));
        if (w)
            return loc * BITS + __builtin_ctzll(w);
        int iter = 0;
        for (++loc; loc < CAPACITY && iter < max_iter; ++loc, ++iter)
        {
            w = ~a[loc];
            if (w)
                return loc * BITS + __builtin_ctzll(w);
        }
        return N;
    }

    i32 find_prev_set(i32 i, i32 max_iter) const noexcept
    {
        --i;
        if (i < 0)
            return -1;
        i32 loc = i / BITS;
        u64 w = a[loc] & (ALL_MASK >> (ALL ^ (i & ALL)));
        if (w)
            return loc * BITS + (ALL ^ __builtin_clzll(w));
        int iter = 0;
        for (--loc; loc >= 0 && iter < max_iter; --loc, ++iter)
        {
            w = a[loc];
            if (w)
                return loc * BITS + (ALL ^ __builtin_clzll(w));
        }
        return -1;
    }

    i32 find_prev_unset(i32 i, i32 max_iter) const noexcept
    {
        --i;
        if (i < 0)
            return -1;
        i32 loc = i / BITS;
        u64 w = (~a[loc]) & (ALL_MASK >> (ALL ^ (i & ALL)));
        if (w)
            return loc * BITS + (ALL ^ __builtin_clzll(w));
        int iter = 0;
        for (--loc; loc >= 0 && iter < max_iter; --loc, ++iter)
        {
            w = ~a[loc];
            if (w)
                return loc * BITS + (ALL ^ __builtin_clzll(w));
        }
        return -1;
    }

    i32 find_last_set() const noexcept
    {
        for (i32 i = CAPACITY - 1; i >= 0; --i)
        {
            u64 w = a[i];
            if (w)
                return i * BITS + (ALL ^ __builtin_clzll(w));
        }
        return -1;
    }

    i32 find_last_unset() const noexcept
    {
        for (i32 i = CAPACITY - 1; i >= 0; --i)
        {
            u64 w = ~a[i];
            if (w)
                return i * BITS + (ALL ^ __builtin_clzll(w));
        }
        return -1;
    }

    // i32 find_kth_set(i32 k) const noexcept {}

    // i32 find_kth_unset(i32 k) const noexcept {}

    // i32 find_kth_next_set(i32 i, i32 k) const noexcept {}

    // i32 find_kth_next_unset(i32 i, i32 k) const noexcept {}

    // i32 find_kth_last_set(i32 k) const noexcept {}

    // i32 find_kth_last_unset(i32 k) const noexcept {}

    // return [l, r)
    u64 slice(const u32 l, const u32 r) const
    {
#ifdef DEBUG
        assert(l <= N);
        assert(r <= N);
#endif
        if (l >= r)
            return 0;
        // 0 <= l < r <= N
        u32 i1 = l / BITS;
        u32 pos1 = l & ALL;
        u32 i2 = (r - 1) / BITS;
        u32 pos2 = (r - 1) & ALL;
        if (i1 == i2)
        {
            return (a[i1] & (ALL_MASK >> (ALL - pos2))) >> pos1;
        }
        else
        {
#ifdef DEBUG
            assert(i2 == i1 + 1);
#endif
            return (a[i1] >> pos1) |
                   ((a[i2] & (ALL_MASK >> (ALL - pos2))) << (BITS - pos1));
        }
    }

    std::string to_string_debug() const
    {
        std::string s(CAPACITY * BITS, '0');
        for (i32 i = 0; i < CAPACITY * BITS; ++i)
            s[CAPACITY * BITS - 1 - i] += (a[i / BITS] >> (i & ALL)) & 1;
        return s;
    }

    friend inline Bitset operator&(const Bitset &x, const Bitset &y) noexcept
    {
        Bitset result = x;
        result &= y;
        return result;
    }
    friend inline Bitset operator|(const Bitset &x, const Bitset &y) noexcept
    {
        Bitset result = x;
        result |= y;
        return result;
    }

    friend inline Bitset operator^(const Bitset &x, const Bitset &y) noexcept
    {
        Bitset result = x;
        result ^= y;
        return result;
    }
    friend std::ostream &operator<<(std::ostream &os, const Bitset &b)
    {
        return os << b.to_string();
    }
    friend std::istream &operator>>(std::istream &os, Bitset &b)
    {
        std::string s = "";
        os >> s;
        b = Bitset(s);
        return os;
    }
};

int main()
{
#ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#else
    freopen("tracks.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
        freopen("con", "r", stdin);
        system("pause"); });
#endif
#endif

    int row, col;
    cin >> row >> col;

    grid_t grid(row);
    for (auto &r : grid)
    {
        cin >> r;
    }

    vvi32 dist(row, vi32(col, INT_MAX));
    dist[0][0] = 1;
    Bitset<(int)8e6> now, later;
    now[0] = true;
    int count_now = 1, count_later = 0;

    int ans = 1;
    while (count_now)
    {
        int k = now.find_first_set();
        now[k] = false;
        count_now--;
        int r = k / col, c = k % col;

        for (int i = 0; i < (int)dx.size(); i++)
        {
            int n_r = r + dx[i];
            int n_c = c + dy[i];

            if (!inside({n_r, n_c}, row, col) ||
                dist[n_r][n_c] != INT_MAX ||
                grid[n_r][n_c] == '.')
            {
                continue;
            }

            if (grid[r][c] == grid[n_r][n_c])
            {
                dist[n_r][n_c] = dist[r][c];
                ans = max(ans, dist[n_r][n_c]);
                now[n_r * col + n_c] = true;
                count_now++;
            }
            else
            {
                dist[n_r][n_c] = dist[r][c] + 1;
                ans = max(ans, dist[n_r][n_c]);
                later[n_r * col + n_c] = true;
                count_later++;
            }
        }

        if (!count_now)
        {
            swap(now, later);
            swap(count_now, count_later);
        }
    }

    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

tracks.cpp:9: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    9 | #pragma region dalykai
      | 
tracks.cpp:33: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   33 | #pragma endregion
      |

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