oj.uz

답안 #888191

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
888191 2023-12-16T10:08:26 Z RedGrey1993 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 465 ms 124376 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); }
template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
 
template <unsigned int MOD>
class ModInt {
public:
    // static unsigned int MOD;
    ModInt(unsigned long long _v = 0) { set_v((_v % MOD + MOD)); }
    explicit operator bool() const { return val != 0; }
    ModInt operator-() const { return ModInt() - *this; }
    ModInt operator+(const ModInt &r) const { return ModInt().set_v(val + r.val); }
    ModInt operator-(const ModInt &r) const { return ModInt().set_v(val + MOD - r.val); }
    ModInt operator*(const ModInt &r) const { return ModInt().set_v((unsigned int)((unsigned long long)(val)*r.val % MOD)); }
    ModInt operator/(const ModInt &r) const { return *this * r.inv(); }
    ModInt &operator+=(const ModInt &r) { return *this = *this + r; }
    ModInt &operator-=(const ModInt &r) { return *this = *this - r; }
    ModInt &operator*=(const ModInt &r) { return *this = *this * r; }
    ModInt &operator/=(const ModInt &r) { return *this = *this / r; }
    // ModInt &operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return *this; }
    unsigned int operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return val; }
    bool operator==(const ModInt &r) const { return val == r.val; }
    bool operator!=(const ModInt &r) const { return val != r.val; }
    ModInt pow(long long n) const {
        ModInt x = *this, r = 1;
        while (n) {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    ModInt inv() const { return pow(MOD - 2); }
    unsigned int get_val() { return val; }
    friend ostream &operator<<(ostream &os, const ModInt &r) { return os << r.val; }
    friend istream &operator>>(istream &is, ModInt &r) { return is >> r.val; }
private:
    unsigned int val;
    ModInt &set_v(unsigned int _v) {
        val = (_v < MOD) ? _v : _v - MOD;
        return *this;
    }
};
// constexpr unsigned int mod = 1e9+7;
constexpr unsigned int mod = 998244353;
using Mint = ModInt<mod>;
 
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif

using Mint2 = ModInt<mod-1>;
// unsigned int ModInt::MOD = 0;
class Solution {
public:
    void Solve() {
        int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        
        int h,w;
        while (cin>>h>>w) {
            vector<string> grid(h);
            rep(i,0,h) cin>>grid[i];

            vector<vi> dis(h, vi(w, numeric_limits<int>::max()));
            deque<pii> q;
            q.emplace_back(mp(0,0));
            dis[0][0] = 0;
            int ans = 0;
            while(!q.empty()) {
                auto u = q.front(); q.pop_front();
                ans = dis[u.first][u.second] + 1;

                rep(i,0,4) {
                    pii v = mp(u.first+dir[i][0], u.second+dir[i][1]);
                    if (v.first <0 || v.first >= h || v.second <0 || v.second >=w) continue;
                    if (grid[v.first][v.second] == '.') continue;
                    // dbg(v);
                    int d = grid[u.first][u.second] != grid[v.first][v.second];
                    if (dis[v.first][v.second] > dis[u.first][u.second] + d) {
                        dis[v.first][v.second] = dis[u.first][u.second] + d;
                        if (d==1) q.emplace_back(v);
                        else q.emplace_front(v);
                    }
                }
            }
            cout << ans << endl;
        }
    }
private:
};
 
// #define USACO 1
void set_io(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if FILE_IO || USACO
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}
 
int main() {
#if USACO
    set_io("odometer");
#else
    set_io("input");
#endif
    Solution().Solve();
 
    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1872 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 1 ms 820 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 2 ms 1112 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 3 ms 980 KB Output is correct
13 Correct 1 ms 840 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 6 ms 1940 KB Output is correct
16 Correct 11 ms 2296 KB Output is correct
17 Correct 5 ms 1880 KB Output is correct
18 Correct 4 ms 1624 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 25 ms 9692 KB Output is correct
3 Correct 139 ms 96680 KB Output is correct
4 Correct 40 ms 22876 KB Output is correct
5 Correct 85 ms 54420 KB Output is correct
6 Correct 465 ms 109832 KB Output is correct
7 Correct 2 ms 728 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 504 KB Output is correct
13 Correct 24 ms 9816 KB Output is correct
14 Correct 14 ms 5724 KB Output is correct
15 Correct 9 ms 6236 KB Output is correct
16 Correct 13 ms 4552 KB Output is correct
17 Correct 68 ms 24704 KB Output is correct
18 Correct 42 ms 24156 KB Output is correct
19 Correct 40 ms 22876 KB Output is correct
20 Correct 33 ms 20820 KB Output is correct
21 Correct 83 ms 56284 KB Output is correct
22 Correct 85 ms 54384 KB Output is correct
23 Correct 134 ms 46964 KB Output is correct
24 Correct 78 ms 54868 KB Output is correct
25 Correct 285 ms 96656 KB Output is correct
26 Correct 279 ms 124376 KB Output is correct
27 Correct 359 ms 113920 KB Output is correct
28 Correct 458 ms 109916 KB Output is correct
29 Correct 461 ms 110092 KB Output is correct
30 Correct 415 ms 109212 KB Output is correct
31 Correct 330 ms 62048 KB Output is correct
32 Correct 317 ms 112344 KB Output is correct