Submission #699690

#	Time	Username	Problem	Language	Result	Execution time	Memory
699690		Tigerpants	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1165 ms	255184 KiB

tracks

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <random>
#include <string>
#include <deque>
#include <queue>
#include <unordered_set>
#include <functional>
#include <stack>

using namespace std;

typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vll> vvll;
typedef vector<vld> vvld;
typedef vector<vvll> vvvll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<pll> vpll;
typedef stack<pll> stpll;
typedef vector<stpll> vstpll;
typedef vector<pld> vpld;
typedef set<ll> sll;
typedef set<pll> spll;
typedef map<pll, ll> mpll_ll;
typedef map<ll, pll> mll_pll;
typedef string str;
typedef vector<str> vstr;
typedef vector<char> vc;
typedef vector<vc> vvc;

#define rep(x, a, b) for (ll x = a; x < b; x++)
#define rev_rep(x, a, b) for (ll x = a; x >= b; x--)
#define itr_rep(type_, x, b) for (type_::iterator x = b.begin(); x != b.end(); x++)
#define mp(a, b) make_pair(a, b)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) a.size()
#define resz(a, b) a.resize(b)
#define sort_all(a) sort(all(a))
#define pb(a) push_back(a)
#define fill_sz(a, b) fill_n(a.begin(), sz(a), b)

const ll INF = 1000000000;

ll H, W;
vvb fox;
vvb rab;
vvc board;
ll N = 1;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> H >> W;

    resz(fox, H);
    resz(rab, H);
    resz(board, H);
    rep(i, 0, H) {
        resz(fox[i], W);
        resz(rab[i], W);
        resz(board[i], W);
        fill_sz(fox[i], false);
        fill_sz(rab[i], false);
    }

    rep(i, 0, H) {
        rep(j, 0, W) {
            cin >> board[i][j];
            fox[i][j] = (board[i][j] == 'F');
            rab[i][j] = (board[i][j] == 'R');
        }
    }

    vpll cur_bfs;
    vpll nxt_bfs;
    vvll dst;
    resz(dst, H);
    rep(i, 0, H) {resz(dst[i], W); fill_sz(dst[i], INF);}

    cur_bfs.push_back(mp(0, 0));
    dst[0][0] = 0;

    ll dx[4] = {0, 1, 0, -1};
    ll dy[4] = {1, 0, -1, 0};

    ll ptr = 0;
    while (not cur_bfs.empty()) {
        pll nx = cur_bfs.back();
        cur_bfs.pop_back();

        if (dst[nx.first][nx.second] != ptr) continue;

        N = ptr;
        
        rep(i, 0, 4) {
            pll nw = mp(nx.first + dx[i], nx.second + dy[i]);
            if ((0 <= nw.first) and (nw.first < H) and (0 <= nw.second) and (nw.second < W)) {
                if (board[nx.first][nx.second] == board[nw.first][nw.second]) {
                    if (dst[nx.first][nx.second] < dst[nw.first][nw.second]) {
                        dst[nw.first][nw.second] = dst[nx.first][nx.second];
                        cur_bfs.push_back(nw);
                    }
                } else if (board[nw.first][nw.second] != '.') {
                    if (dst[nx.first][nx.second] + 1 < dst[nw.first][nw.second]) {
                        dst[nw.first][nw.second] = dst[nx.first][nx.second] + 1;
                        nxt_bfs.push_back(nw);
                    }
                }
            }
        }

        if (cur_bfs.empty()) {
            swap(nxt_bfs, cur_bfs);
            ptr++;
        }
    }

    cout << N + 1 << endl;

    return 0;
}

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