Submission #675968

#	Time	Username	Problem	Language	Result	Execution time	Memory
675968		_samit_	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	746 ms	96236 KiB

tracks

//	  Author: Samit Maharjan
//	  Created: 2022-12-28 22:15

#include "bits/stdc++.h"
using namespace std;

//Typedefs
typedef long long       ll;
typedef long double     ld;

typedef pair<int, int>  pi;
typedef pair<ll, ll>    pl;
typedef pair<ld, ld>    pd;

typedef vector<int>     vi;
typedef vector<ll>      vl;
typedef vector<ld>      vd;
typedef vector<pi>      vpi;
typedef vector<pl>      vpl;
typedef vector<pd>      vpd;

//Definitions
#define FOR(i, a, b)    for(int i = a; i < b; i++)
#define F0R(i, a)       for(int i = 0; i < a; i++)
#define FORr(i, a, b)   for(int i = b - 1; i >= a ; i--) 
#define F0Rr(i, a)      for(int i = a - 1; i >= 0; i--)
#define trav(i, x)      for (auto &i : x)

#define mp              make_pair
#define pb              push_back
#define f               first
#define s               second
#define all(x)          x.begin(), x.end()
#define ins             insert
#define pcount          __builtin_popcount
#define sz(x)           (int)x.size()

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
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<class T> T inv(T a, T b){ return a == 1 ? 1 : ( (T)1 - inv(b % a, a) * b) / a + b; }
template<class T> T binpow(T a, T b){ return b == 0 ? 1 : (b & 1) ? a * binpow(a * a, b >> 1) : binpow(a * a, b >> 1); }
template<class T> T gcd(T a, T b){ return b ? gcd(b, a % b) : a; }

// Debugging
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...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[93m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

const int N = 4000;
int dist[N * N], g[] = {1, 0, -1, 0, 1};
char grid[N + 1][N + 1];

void solve(){
    int m, n;   cin >> m >> n;
    F0R(i, m){
        F0R(j, n){
            cin >> grid[i][j];
            dist[i * n + j] = 0;       
        }
    }
    auto check = [&](int x, int y) -> bool{
        return x >= 0 && x < m && y >= 0 && y < n;
    };
    // will have at least one animal
    dist[0] = 1;
    deque<int> q;   q.push_back(0);
    int res = 0;
    while(!q.empty() ){
        int node = q.front();   q.pop_front();
        int x = node / n, y = node % n;
        res = max(res, dist[node]);
        for(int i = 0; i < 4; ++i){
            int nx = x + g[i], ny = y + g[i + 1];
            if(check(nx, ny) && grid[nx][ny] != '.' && dist[nx * n + ny] == 0){
                if(grid[nx][ny] == grid[x][y]){
                    q.push_front(nx * n + ny);
                    dist[nx * n + ny] = dist[node];
                } else {
                    q.push_back(nx * n + ny);
                    dist[nx * n + ny] = dist[node] + 1;
                }
            }
        }
    }
    cout << res << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;  
    //cin >> t;
    while(t--)
        solve();
    return 0;
}

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