제출 #490978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490978		sberens	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1723 ms	113388 KiB

tracks

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;


using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)


using ll = long long;
using ld = long double;

template<typename T>
using vv = vector<vector<T>>;

using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;

using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;

template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;

const ll M = 1000000007;
const ll infll = M * M;

vii dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

vii adjc(int x, int y) {
    vii res;
    for (auto [dx, dy] : dirs) {
        res.pb({x + dx, y + dy});
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    vector<string> g(h);
    F0R(r, h) {
        cin >> g[r];
    }
    int res = 0;
    int p = '.';
    deque<ii> q; // r, c
    q.push_front({0, 0});
    vvi seen(h, vi(w));
    seen[0][0] = 1;
    while (!q.empty()) {
        assert(q.size() <= h * w);
        auto [r, c] = q.front(); q.pop_front();
        if (g[r][c] != p) res++;
        p = g[r][c];
        for (auto [nr, nc] : adjc(r, c)) {
            if (0 <= nr && nr < h && 0 <= nc && nc < w && seen[nr][nc] == 0 && g[nr][nc] != '.') {
                if (g[nr][nc] == p) q.push_front({nr, nc});
                else q.push_back({nr, nc});
                seen[nr][nc] = 1;
            }
        }
    }
    cout << res << '\n';

}

컴파일 시 표준 에러 (stderr) 메시지

In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
                 from tracks.cpp:3:
tracks.cpp: In function 'int main()':
tracks.cpp:74:25: warning: comparison of integer expressions of different signedness: 'std::deque<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |         assert(q.size() <= h * w);
      |                ~~~~~~~~~^~~~~~~~

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