oj.uz

답안 #915203

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915203 2024-01-23T13:24:07 Z DaBest Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 642 ms 252424 KB 
////------------> FLS.
#include <bits/stdc++.h>
using namespace std;

using ll = long long; using ld = long double;
#define int long long
#define double long double
#define endl '\n'
#define FLS ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define vin(a) for(auto&XX:a)cin>>XX;//idk y but it restricts my thought process at times
#define vout(v) for (auto XX: v)cout<<XX<<' ';cout<<endl;
#define vvin(a) for(auto& b : a) {for(auto& x : b) cin>>x;}
#define vvout(a) for(auto& b: a) {for(auto& x : b) {cout<<x<<" ";}cout<<endl;}
#define meh {cout<<"NO"<<endl;return;}
#define yay {cout<<"YES"<<endl;return;}
#define IMmeh {cout<<"NO"<<endl;continue;}
#define IMyay {cout<<"YES"<<endl;continue;}
//=======================================================------------------------------------------------------
void print(int t) {cout << t;} 
void print(string t) {cout << t;}
void print(char t) {cout << t;}
void print(double t) {cout << t;}
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(pair <T, V> p) {cout << "{"; print(p.first); cout << ","; print(p.second); cout << "}";}
template <class T> void print(vector <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]\n";}
template <class T> void print(set <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]\n";}
template <class T> void print(multiset <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]\n";}
template <class T, class V> void print(map <T, V> v) {cout << "[ "; for (auto i : v) {print(i); cout << " ";} cout << "]\n";}
//=======================================================------------------------------------------------------
// #define pow2(x) (1ll<<(x))
template <typename T, typename U> T cdiv(T x, U y) {assert(y!=0);return (x > 0 ? (x + y - 1) / y : x / y);}
template <typename T, typename U> T fdiv(T x, U y) {assert(y!=0);return (x > 0 ? x / y : (x - y + 1) / y);}
template <typename T> int sgn(T val) {return (T(0) < val) - (val < T(0));} //sgn(x) gives -1/0/1
//returns integer, only works if a is a guarantee perfect square
long long sqroot(long long a){long long b = (long long) sqrtl(a);if ((b + 1) * (b + 1) == a){b++;}return b;}
constexpr ll inf = 1E18;
//(raise(a,b) = a^b) [a,b > 0].
long long raise(long long a, long long b) {long long res = 1;for(int i = 0; i<b; i++) {if(inf/res < a) return 0;res *= a;}return res;}
bool isSquare(int n) {int r = sqrtl(1.0L * n);return r*r == n;}
//=======================================================----------------------------------
const int MAX = 200007; //2*10^5 + 7
const int mod = 1000000007; //1e9+7, comment it out if u want to use the other MOD
// // const int MOD = 998244353;
// const double EPS=1E-9;
// const int MAXN = 10000010; //1e7+10
//----------------

int dx[4]{1, -1, 0, 0};
int dy[4]{0, 0, 1, -1};
vector<vector<int>> depth(4000, vector<int>(4000));
vector<string> snow(4000);

void solve() {

    int n, m; cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> snow[i];

    auto inside = [&](int x, int y) -> bool {
        return (x >= 0 && x < n && y >= 0 && y < m && snow[x][y] != '.');
    };

    int ans = 1;
    deque<pair<int, int>> dq;
    dq.push_back({0, 0}); depth[0][0] = 1;

    while(dq.empty() == false) {
        pair<int, int> node_coords = dq.front();
        dq.pop_front();
        ans = max(ans, depth[node_coords.first][node_coords.second]);

        for(int direction = 0; direction < 4; direction++) {
            int x_new = node_coords.first + dx[direction]; int y_new = node_coords.second + dy[direction];
            if(inside(x_new, y_new) == true) {
                if(depth[x_new][y_new] != 0) {
                    // if depth[x][y] has already been updated, that means the node {x,y}..
                    //.. has already been reached by a shorter route.
                    // so dont update depth[x][y]; we want to retain the shortest value for depth of a node.
                } else {
                    if(snow[node_coords.first][node_coords.second] == snow[x_new][y_new]) {
                        // same animal? -> weight zero. keep the depth same and push_front.
                        depth[x_new][y_new] = depth[node_coords.first][node_coords.second];
                        dq.push_front({x_new, y_new});
                    } else {
                        // different animal? -> weight one. increment the depth, and push_back
                        depth[x_new][y_new] = depth[node_coords.first][node_coords.second] + 1;
                        dq.push_back({x_new, y_new});
                    }
                }
            }
        }
    }
    cout << ans << endl;
    // each depth level represents an animal
    // the deepest level is the first animal that had crossed the meadow
    // the least level (1) is the last (recentmost) animal that had crossed the meadow.

    // cout<<"===="<<endl;

}

/*ngu, lesgo*/
int32_t main() {
    FLS
    //cout<<fixed<<setprecision(20)<<x; //-> for printing a double 'x'.

    // freopen("", "r", stdin);
    // freopen("", "w", stdout);
    
    int TT=1;
    // cin>>TT; //comment out this line if only 1 test case is needed
    while(TT--) {
        solve();
    }
 
    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 126556 KB Output is correct
2 Correct 75 ms 125776 KB Output is correct
3 Correct 65 ms 125892 KB Output is correct
4 Correct 68 ms 126568 KB Output is correct
5 Correct 67 ms 126108 KB Output is correct
6 Correct 68 ms 125872 KB Output is correct
7 Correct 68 ms 125888 KB Output is correct
8 Correct 66 ms 125780 KB Output is correct
9 Correct 67 ms 125988 KB Output is correct
10 Correct 67 ms 125964 KB Output is correct
11 Correct 74 ms 126032 KB Output is correct
12 Correct 70 ms 126172 KB Output is correct
13 Correct 67 ms 126132 KB Output is correct
14 Correct 71 ms 125988 KB Output is correct
15 Correct 78 ms 126524 KB Output is correct
16 Correct 79 ms 126584 KB Output is correct
17 Correct 72 ms 126292 KB Output is correct
18 Correct 71 ms 126544 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 125812 KB Output is correct
2 Correct 92 ms 129108 KB Output is correct
3 Correct 198 ms 159272 KB Output is correct
4 Correct 116 ms 133460 KB Output is correct
5 Correct 169 ms 144272 KB Output is correct
6 Correct 642 ms 186604 KB Output is correct
7 Correct 68 ms 126024 KB Output is correct
8 Correct 68 ms 125956 KB Output is correct
9 Correct 66 ms 125912 KB Output is correct
10 Correct 75 ms 125908 KB Output is correct
11 Correct 68 ms 125776 KB Output is correct
12 Correct 67 ms 125776 KB Output is correct
13 Correct 92 ms 128944 KB Output is correct
14 Correct 82 ms 127800 KB Output is correct
15 Correct 82 ms 127828 KB Output is correct
16 Correct 79 ms 127272 KB Output is correct
17 Correct 131 ms 134244 KB Output is correct
18 Correct 124 ms 134360 KB Output is correct
19 Correct 112 ms 133712 KB Output is correct
20 Correct 99 ms 132956 KB Output is correct
21 Correct 144 ms 144976 KB Output is correct
22 Correct 165 ms 144464 KB Output is correct
23 Correct 197 ms 141972 KB Output is correct
24 Correct 144 ms 144612 KB Output is correct
25 Correct 529 ms 159316 KB Output is correct
26 Correct 379 ms 252424 KB Output is correct
27 Correct 452 ms 212292 KB Output is correct
28 Correct 588 ms 186564 KB Output is correct
29 Correct 599 ms 183204 KB Output is correct
30 Correct 553 ms 194336 KB Output is correct
31 Correct 417 ms 147920 KB Output is correct
32 Correct 405 ms 189860 KB Output is correct