oj.uz

답안 #991151

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
991151 2024-06-01T12:47:49 Z Hadi_Alhamed Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 402 ms 130652 KB 
// to live is to die
#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;

typedef long long int ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpl;
#define Clear(a, n)              \
    for (int i = 0; i <= n; i++) \
    {                            \
        a[i] = 0;                \
    }
#define clearMat(a, n, m, d)         \
    for (int i = 0; i <= n; i++)     \
    {                                \
        for (int j = 0; j <= m; j++) \
            a[i][j] = d;             \
    }
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define PB push_back
#define PF push_front
#define MP make_pair
#define F first
#define S second
#define rep(i, n) for (int i = 0; i < n; i++)
#define repe(i, j, n) for (int i = j; i < n; i++)
#define SQ(a) (a) * (a)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define Rrep(i, start, finish) for (int i = start; start >= finish; i--)

#define forn(i, Start, End, step) for (int i = Start; i <= End; i += step)
#define rforn(i, Start, End, step) for (int i = Start; i >= End; i -= step)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
// ll arr[SIZE];
/*
how to find n % mod ; n < 0?
x = (n+mod)%mod
if(x < 0) x += mod;
*/
void __print(int x)
{
    cerr << x;
}
void __print(long x)
{
    cerr << x;
}
void __print(long long x)
{
    cerr << x;
}
void __print(unsigned x)
{
    cerr << x;
}
void __print(unsigned long x)
{
    cerr << x;
}
void __print(unsigned long long x)
{
    cerr << x;
}
void __print(float x)
{
    cerr << x;
}
void __print(double x)
{
    cerr << x;
}
void __print(long double x)
{
    cerr << x;
}
void __print(char x)
{
    cerr << '\'' << x << '\'';
}
void __print(const char *x)
{
    cerr << '\"' << x << '\"';
}
void __print(const string &x)
{
    cerr << '\"' << x << '\"';
}
void __print(bool x)
{
    cerr << (x ? "true" : "false");
}

template<typename T, typename V>
void __print(const pair<T, V> &x)
{
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template<typename T>
void __print(const T &x)
{
    int f = 0;
    cerr << '{';
    for (auto &i: x) cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print()
{
    cerr << "]\n";
}
template <typename T, typename... V>
void _print(T t, V... v)
{
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}
#ifndef ONLINE_JUDGE
#define db(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define db(x...)
#endif

// order_of_key(k): # of elements less than k (which is the index of x = k)
// find_by_order(k); iterator of the k-th element

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>
bool ckmin(T &a, const T &b)
{
    return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T &a, const T &b)
{
    return a < b ? a = b, 1 : 0;
}
template <typename T>
istream &operator>>(istream &in, vector<T> &a)
{
    for (auto &x : a)
        in >> x;
    return in;
};
template <typename T>
ostream &operator<<(ostream &out, vector<T> &a)
{
    for (auto &x : a)
        out << x << ' ';
    return out;
};

// priority_queue<data type , the container that would hold the values , greater<pair<int,int>>>
// greater means that we want the smallest value on top
// less means that we want the largest
// x ^ (n) mod m = ( (x mod m)^(n) ) mod m
char to_char(int num)
{
    return (char)(num + '0');
}

ll const MAX = 1e18 + 1;
ll const oo = 1e18 + 1;
ll const INF = 1e9 + 10;
const ll MOD = 1e9 + 7;
ll const SIZE = 2e5 + 900;
const int LOG = 20;

template <typename T, typename T2>
void add(T &X, T2 Y)
{
    X += Y;
    if (X >= MOD)
    {
        X -= MOD;
    }
}

template <typename T, typename T2>
T mult(T X, T2 Y)
{
    return X * Y % MOD;
}

void setIO(string s)
{
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
// x & (-x) give me the minBit of x
//  x & (x - 1) turns off rightmost bit

int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , 1 , -1};
int N  , M  , depth[4001][4001] , answer = 1;
string snow[4000];
bool valid(int x, int y) {
	return (x > -1 && x < N && y > -1 && y < M && snow[x][y] != '.');
}
void solve()
{

        cin >> N >> M;
        rep(i , N)
        {
            cin >> snow[i];
        }
        depth[0][0] = 1;
        deque<pi>dq;
        dq.PB({0 , 0});
        while(dq.size())
        {
            pi cur = dq.front();
            dq.pop_front();
            answer = max(answer ,depth[cur.F][cur.S]);
            for(int i = 0 ; i < 4 ; i ++)
            {
                int x = cur.F + dx[i] , y = cur.S + dy[i];
                if(valid(x , y) && depth[x][y] == 0)
                {
                    if(snow[x][y] == snow[cur.F][cur.S])
                    {
                        depth[x][y] = depth[cur.F][cur.S];
                        dq.push_front({x, y});
                    }else{
                        depth[x][y] = depth[cur.F][cur.S] + 1;
                        dq.PB({x , y});
                    }
                }
            }
        }
        cout << answer << "\n";

}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //    setIO("");

    int T = 1;
//    cin >> T;

    while (T--)
    {
        solve();
    }
    return 0;
}

/* stuff you should look for
 * WRITE STUFF DOWN,  ON PAPER
 * BFS THEN DFS
 * int overflow, array bounds
 * special cases (n=1?)
 * do sm th instead of nothing and stay organized
 * DON'T GET STUCK ON ONE APPROACH
 * (STUCK?)******** Try to simplify the problem(keeping in mind the main problem), ():
 * 1- problem to subProblem
 * 2- from simple to complex: start with a special
 *    problem and then try to update the solution for general case
 *    -(constraints - > solve it with none , one,two ... of them till you reach the given problem
      -(no constraints - > try to give it some)
      -how a special case may be incremented
 * 3-Simplification by Assumptions
 * REVERSE PROBLEM
 * PROBLEM ABSTRACTION
 * SMALL O BSERVATIONS MIGHT HELP ALOT
 * WATCH OUT FOR TIME
 * RETHINK YOUR IDEA,BETTER IDEA, APPROACH?
 * CORRECT IDEA, NEED MORE OBSERVATIONS
 * CORRECT APPROACH, WRONG IDEA
 * WRONG APPROACH
 * THINK CONCRETE THEN SYMBOL,
 * having the solution for the first m state , can we solve it for m + 1 ?
 * in many cases incremental thinking needs data sorting
 */

Compilation message

tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:203:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:204:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 3928 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 588 KB Output is correct
4 Correct 4 ms 3672 KB Output is correct
5 Correct 2 ms 2140 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 4 ms 2140 KB Output is correct
13 Correct 2 ms 2140 KB Output is correct
14 Correct 2 ms 2124 KB Output is correct
15 Correct 7 ms 3848 KB Output is correct
16 Correct 8 ms 3932 KB Output is correct
17 Correct 6 ms 3672 KB Output is correct
18 Correct 4 ms 3676 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 15960 KB Output is correct
2 Correct 27 ms 12124 KB Output is correct
3 Correct 140 ms 75276 KB Output is correct
4 Correct 48 ms 29520 KB Output is correct
5 Correct 114 ms 51536 KB Output is correct
6 Correct 390 ms 109900 KB Output is correct
7 Correct 10 ms 16732 KB Output is correct
8 Correct 7 ms 15964 KB Output is correct
9 Correct 2 ms 900 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 7 ms 16476 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 27 ms 11900 KB Output is correct
14 Correct 15 ms 8024 KB Output is correct
15 Correct 15 ms 10332 KB Output is correct
16 Correct 14 ms 4956 KB Output is correct
17 Correct 68 ms 25328 KB Output is correct
18 Correct 47 ms 32336 KB Output is correct
19 Correct 53 ms 29412 KB Output is correct
20 Correct 36 ms 22612 KB Output is correct
21 Correct 93 ms 50564 KB Output is correct
22 Correct 110 ms 51540 KB Output is correct
23 Correct 141 ms 42296 KB Output is correct
24 Correct 88 ms 47440 KB Output is correct
25 Correct 195 ms 96472 KB Output is correct
26 Correct 205 ms 130652 KB Output is correct
27 Correct 273 ms 122848 KB Output is correct
28 Correct 382 ms 110056 KB Output is correct
29 Correct 402 ms 108232 KB Output is correct
30 Correct 362 ms 112380 KB Output is correct
31 Correct 311 ms 72072 KB Output is correct
32 Correct 235 ms 108268 KB Output is correct