Submission #753684

#	Time	Username	Problem	Language	Result	Execution time	Memory
753684		Mazhavil	Tracks in the Snow (BOI13_tracks)	C++17	91.25 / 100	641 ms	125188 KiB

tracks

#include "bits/stdc++.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
using namespace std;
 
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<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define rep(i, a) for (ll i=0; i<(a); i++)
#define repd(i,a) for (ll i = (a)-1; i >= 0; i--)
#define repi(i,a,b) for(ll i=(a); i<(b); i++)
#define repi_d(i,a,b) for(ll i=b-1; i>=a; i--)
#define trav(a,x) for (auto& a : x) //can be used everywhere
#define tr(a,x) for(auto a : x) //only for cout
#define deb(x) cout<<#x<< "=" <<x<<endl
#define deb2(x,y) cout<<#x<< "=" <<x<< "," <<#y<< "=" <<y<<endl
 
#define num(a,s) count(a.begin(),a.end(),s)     
#define nsort(a) sort(a.begin(),a.end())        //normal sort
#define rsort(a) sort(a.rbegin(),a.rend())  //reverse sort-descending order
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define PI 3.1415926535897932384626
#define max3(a,b,c) max(a,max(b,c))
const ll MOD = 1000000007;
const int MAXN = 1e6;
const char nl = '\n';
 
//BINARY EXPONENTIATION
/** Computes x^n modulo m in O(log p) time. */
ll binpow(ll a,ll b,ll m){
    ll res = 1;
    while (b){
        if (b&1) res = (res*a)%m;
        a = (a*a)%m;
        b>>=1;
    }
    return res;
}
 
//Multiplication of two long numbers mdulo M
ll binmul(ll n,ll m,ll M){
ll ans =0;
while(m){
    if(m&1){
        ans = (ans+n)%M;
    }
    n = (n+n)%M;
    m>>1;
}
return ans;
}
ll sq(ll n){
    ll a = sqrt(n);
    a++;
    if(a*a<=n){
        return a;
    }
    a--;
    if(a*a<=n){
        return a;
    }
    a--;
    return a;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
 
    int tt=1;
   // cin >>tt;
    while(tt--) {
       int n,m;cin>>n>>m;
       vector<string>v(n);
       for(int i=0;i<n;i++){
        cin>>v[i];
       }
       int mx=0;
       vector<vi>d(n,vi(m,1e6));
       d[0][0]=0;
       deque<pair<int,int>>dq;
       dq.push_front({0,0});
       int dr[]={-1,0,1,0};
       int dc[]={0,-1,0,1};
        while(!dq.empty()){
            pair<int,int>p=dq.front();
            int r=p.f,c=p.s;
            dq.pop_front();
            for(int i=0;i<4;i++){
                if(r+dr[i]<n and r+dr[i]>=0 and c+dc[i]<m and c+dc[i]>=0){
                    
                    int ur=r+dr[i],uc=c+dc[i];
                    if(v[ur][uc]=='.')continue;
                    int w=1;
                    if(v[ur][uc]==v[r][c])w=0;
                    else w=1;

                    if(d[r][c]+w<d[ur][uc]){
                        d[ur][uc]=d[r][c]+w;
                        mx=max(mx,d[ur][uc]);
                        if(w==0){
                            dq.push_front({ur,uc});
                        }else{
                            dq.push_back({ur,uc});
                        }
                    }
                    
                }
            }
        }
        int ans=mx+1;
        cout<<ans<<endl;

    }
 
return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'll binmul(ll, ll, ll)':
tracks.cpp:64:6: warning: statement has no effect [-Wunused-value]
   64 |     m>>1;
      |     ~^~~

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