Submission #853155

#	Time	Username	Problem	Language	Result	Execution time	Memory
853155		shiv_213	Tracks in the Snow (BOI13_tracks)	C++98	100 / 100	488 ms	236368 KiB

tracks

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

using namespace __gnu_pbds;

using namespace std;
#ifndef ONLINE_JUDGE
// #include "DEBUG.h"
#else
#define debug(...) 69
#endif
#define IOS    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define int long long
#define double long double
#define endl '\n'
#define Endl cout<<'\n';
#define MOD 1000000007
const int M = 1e18;
const int mod=1e9+7;
double pi = 2 * acos(0.0);
#define I =in()
#define S =sin()
#define C =chin()
#define rep(i,a,b)      for(int i=a;i<b;i++)
#define repo(i,a,b)      for(int i=a;i>=b;i--)
#define vfill(arr)       for(auto &x:arr)cin>>x;
#define Vfill(arr)      for(auto &x:arr)for(auto &y:x)cin>>y;
#define Fill(arr)       for(int i =0;i<n;i++){cin>>arr[i].first>>arr[i].second;}


#define all(x)          begin(x), end(x)
#define unik(vec)       vec.resize(unique(all(vec)) - vec.begin());
#define unikSort(vec)   sort(all(vec));vec.resize(unique(all(vec)) - vec.begin());

#define vi              vector<int>
#define pii              pair<int,int>
#define N               n
#define vvi             vector<vector<int>>
#define pii             pair<int,int>
#define pci             pair<char,int>
#define psi             pair<string,int>
#define mii             map<int,int>
#define msi             map<string,int>
#define mci             map<char,int>
#define vii             vector<pair<int,int>>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

#define vprint(arr)     for(auto &x:arr)cout<<x<<" "; 
#define Vprint(arr)     for(auto &x:arr){for(auto &y:x)cout<<y<<" ";cout<<endl;}
#define sprint(arr)     for(auto &x:arr)cout<<x;cout<<endl;
#define Sprint(arr)     for(auto &x:arr){for(auto y:x)cout<<y;cout<<endl;}

inline int in(){int x;cin >> x;return x;}inline string sin(){string x;cin >> x;return x;}inline char chin(){char x;cin >> x;return x;}inline int In(){int x;cin >> x;return x;}
// ==========================================================================================================
long long binpow(long long a, long long b) {if (b == 0)return 1;long long res = binpow(a, b / 2);if (b % 2)return res * res * a;else return res * res;}
// long long binpowMOD(long long a, long long b, long long m) {a %= m;long long res = 1;while (b > 0) {if (b & 1)res = res * a % m;a = a * a % m;b >>= 1;}return res;}
// ==========================================================================================================

// int powm(int a, int b, int mod) { int res = 1; while (b > 0) { if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1; } return res; }  //power modulo m
// void extendgcd(int a, int b, int* v) { if (b == 0) { v[0] = 1; v[1] = 0; v[2] = a; return; } extendgcd(b, a % b, v); int x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return; } //pass an array of size 3
// int mminv(int a, int b) { int arr[3]; extendgcd(a, b, arr); return arr[0]; } //for non prime b
// int mminvprime(int a, int b) { if (a % b == 0) return -1; return powm(a, b - 2, b); } //for prime only
// const int SIZE = 10005; 
// int fact[SIZE], ifact[SIZE];
// void gen_factorial(int n, int mod) { fact[0] = fact[1] = ifact[0] = ifact[1] = 1; for (int i = 2; i <= n; i++) { fact[i] = (i * fact[i - 1]) % mod; } ifact[n] = mminvprime(fact[n], mod); for (int i = n - 1; i >= 2; i--) { ifact[i] = ((i + 1) * ifact[i + 1]) % mod; } }
// int choose(int n, int r, int m) { int val1 = fact[n]; int val2 = ifact[n - r]; int val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m; } 

// be careful with mod subtraction - if it is negative than add mod.
// go for another approach
// time complexity
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
vector<string>arr;
int depth[4005][4005];
bool in(int x, int y, int n, int m){
    return (x>=0&&x<n&&y>=0&&y<m && arr[x][y]!='.');
}
void solve(int xx){	 
    int n I,m I;
    arr.resize(n);vfill(arr);
    
    deque<pii>q;
    int ans = 1;
    q.push_back({0,0});
    depth[0][0]=1;

    while(!q.empty()){

        int x=q.front().first,y=q.front().second;
        q.pop_front();
        ans = max(ans,depth[x][y]);

        rep(i,0,4){

            int newx=x+dx[i];
            int newy=y+dy[i];


            if(in(newx,newy,n,m)&&depth[newx][newy]==0){
                if(arr[x][y]!=arr[newx][newy]){
                    q.push_back({newx,newy});
                    depth[newx][newy]=depth[x][y]+1;
                }else{
                    q.push_front({newx,newy});
                    depth[newx][newy]=depth[x][y];
                }
            }
        }
    }
   
    cout<<ans<<endl;


}

// =======================================================================================================
signed main(){
    IOS;
    int t =1,xx=0 ;
    // cin>>t;
    while (t--){solve(xx++);}return 0;
}
// =======================================================================================================

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