oj.uz

Submission #858788

# Submission time Handle Problem Language Result Execution time Memory
858788 2023-10-09T07:47:55 Z wibulord Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 638 ms 132992 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define db long double
#define fi first
#define se second
#define pb emplace_back

#define vi vector<int>
#define vii vector<pair<int,int>>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pdd pair<db, db>
#define iii pair<int, pair<int, int> >

#define ms(s, n) memset(s, n, sizeof(s))
#define all(a) a.begin(), a.end()
#define uni(a) (sort(all(a)), a.resize(unique(all(a))-a.begin()))
#define sz(a) int((a).size())

#define bit(x) bitset<10>((x))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (1 &((x) >> (i)))
#define clz(x) __builtin_clz((x))
#define ctz(x) __builtin_ctz((x))
#define popc(x) __builtin_popcount((x))
#define clzll(x) __builtin_clzll((x))
#define ctzll(x) __builtin_ctzll((x))
#define popcll(x) __builtin_popcountll((x))

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define F0R(i, b) for (int i = 0, _b = (b); i < _b; ++i)
#define FORd(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define F0Rd(i, b) for (int i = (b)-1; i >= 0; i--)
#define rep(i, a) for (auto i : a)

using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

void print(int x) {cerr << x;}
void print(long long x) {cerr << x;}
void print(long double x) {cerr << x;}
void print(double x) {cerr << x;}
void print(unsigned long long x) {cerr << x;}
void print(char x) {cerr << x;}
void print(bool x) {cerr << (x ? "True" : "False");}
void print(string x) {cerr << x;}

template <typename T,typename H>
void print(pair<T,H> a) {cerr << "("; print(a.fi); cerr << ','; print(a.se); cerr << ')';}
template <typename T>
void print(T vec) {int cnt=0; cerr << "{"; rep(x,vec) cerr << (cnt++?",":""), print(x); cerr << '}';}

void show() {}
template <typename Head, typename ...Tail>
void show(Head H, Tail ...T){
    print(H);
    if (sizeof...(T)) cerr << ", ";
    show(T...);
}
#define debug(X...) cerr << "LINE "  << __LINE__ << " - " <<  "[" << #X << "] = [", show(X), cerr << "]\n"

template<typename T1,typename T2> bool ckmax(T1 &x,const T2 &y){if(x<y){x=y; return 1;} return 0;}
template<typename T1,typename T2> bool ckmin(T1 &x,const T2 &y){if(y<x){x=y; return 1;} return 0;}

inline int gcd(int x,int y){while(y){int tmp=y;y=x%y;x=tmp;} return (x);}
inline int lcm(int x,int y){return (int)(x*y)/gcd(x,y);}

void read(){}
template <typename Head, typename ...Tail>
void read(Head &H, Tail &...T)
{
    int sign = 0;
    char c;
    for (c = getchar(); !isdigit(c); c = getchar())
        if (c == '-') sign = 1;
    H = c - '0';
    for (c = getchar(); isdigit(c); c = getchar())
        H = H * 10 + c - '0';
    if (sign) H = -H;
    read(T...);
}

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return l + rd()% (r-l+1);}

const int MOD = 1000000007;
const int mod = 998244353;
const int oo = 1061109567;
const long long INF = 4557430888798830399;
const double PI = acos(-1);
const int N = 4e3 + 1, M = 1e2 + 5;

/*
     /\_/\
    (= ._.)
    / >?  \>$
*/
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};

int n, m;
int d[N][N];
char a[N][N];

bool check(int x, int y){
    if(x < 1 || y < 1) return 0;
    if(x > n || y > m) return 0;
    if(d[x][y] || a[x][y] == '.') return 0;
    return 1;
}

void sol(){
    cin >> n >> m;
    FOR(i, 1, n) FOR(j, 1, m) cin >> a[i][j];
    int ans = 0; 
    deque<pii> dq; dq.push_back({1, 1});
    d[1][1] = 1;
    while(sz(dq)){
        int x = dq[0].fi;
        int y = dq[0].se;
        dq.pop_front();
        ckmax(ans, d[x][y]);
        F0R(i, 4){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(check(nx, ny)){
                if(a[x][y] == a[nx][ny]){
                    d[nx][ny] = d[x][y];
                    dq.push_front({nx ,ny});
                }
                else{
                    d[nx][ny] = d[x][y] + 1;
                    dq.push_back({nx ,ny});
                }
            }
        }
    }
    cout << ans << endl;
    // FOR(i, 1, n) FOR(j, 1, m) cout << d[i][j] << " \n"[j == m];
}

signed main(){
    #define TASK "nhap"
    if(fopen(TASK".inp", "r")){
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    fast; int t = 1;
//    cin >> t;
    while(t--) sol();
    clog << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7516 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 7 ms 7360 KB Output is correct
5 Correct 3 ms 5724 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4568 KB Output is correct
9 Correct 1 ms 4696 KB Output is correct
10 Correct 3 ms 5468 KB Output is correct
11 Correct 2 ms 5468 KB Output is correct
12 Correct 6 ms 6236 KB Output is correct
13 Correct 3 ms 5852 KB Output is correct
14 Correct 3 ms 5980 KB Output is correct
15 Correct 11 ms 7444 KB Output is correct
16 Correct 15 ms 7772 KB Output is correct
17 Correct 9 ms 7260 KB Output is correct
18 Correct 7 ms 7256 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 32224 KB Output is correct
2 Correct 43 ms 18048 KB Output is correct
3 Correct 264 ms 73692 KB Output is correct
4 Correct 76 ms 35176 KB Output is correct
5 Correct 193 ms 55376 KB Output is correct
6 Correct 638 ms 107732 KB Output is correct
7 Correct 11 ms 32856 KB Output is correct
8 Correct 9 ms 32348 KB Output is correct
9 Correct 2 ms 2520 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 9 ms 32688 KB Output is correct
12 Correct 1 ms 4956 KB Output is correct
13 Correct 42 ms 18164 KB Output is correct
14 Correct 25 ms 12756 KB Output is correct
15 Correct 21 ms 15184 KB Output is correct
16 Correct 21 ms 7916 KB Output is correct
17 Correct 108 ms 30996 KB Output is correct
18 Correct 85 ms 37616 KB Output is correct
19 Correct 71 ms 35216 KB Output is correct
20 Correct 63 ms 28724 KB Output is correct
21 Correct 164 ms 54344 KB Output is correct
22 Correct 202 ms 55528 KB Output is correct
23 Correct 216 ms 45648 KB Output is correct
24 Correct 160 ms 51556 KB Output is correct
25 Correct 365 ms 94644 KB Output is correct
26 Correct 374 ms 132992 KB Output is correct
27 Correct 499 ms 115972 KB Output is correct
28 Correct 624 ms 107988 KB Output is correct
29 Correct 611 ms 106072 KB Output is correct
30 Correct 562 ms 109520 KB Output is correct
31 Correct 502 ms 77032 KB Output is correct
32 Correct 436 ms 105740 KB Output is correct