oj.uz

Submission #753684

# Submission time Handle Problem Language Result Execution time Memory
753684 2023-06-05T17:07:28 Z Mazhavil Tracks in the Snow (BOI13_tracks) C++17
91.25 / 100
 641 ms 125188 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1740 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 6 ms 1484 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 5 ms 844 KB Output is correct
13 Correct 3 ms 844 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 8 ms 1844 KB Output is correct
16 Correct 10 ms 1740 KB Output is correct
17 Correct 7 ms 1748 KB Output is correct
18 Correct 6 ms 1508 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 33 ms 9676 KB Output is correct
3 Correct 184 ms 96528 KB Output is correct
4 Correct 51 ms 22732 KB Output is correct
5 Incorrect 50 ms 54212 KB Output isn't correct
6 Correct 641 ms 110460 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 33 ms 9672 KB Output is correct
14 Correct 20 ms 5732 KB Output is correct
15 Correct 13 ms 6228 KB Output is correct
16 Correct 17 ms 4172 KB Output is correct
17 Correct 84 ms 24580 KB Output is correct
18 Correct 50 ms 24152 KB Output is correct
19 Correct 49 ms 22728 KB Output is correct
20 Correct 40 ms 20852 KB Output is correct
21 Correct 103 ms 56060 KB Output is correct
22 Incorrect 50 ms 54196 KB Output isn't correct
23 Correct 163 ms 46748 KB Output is correct
24 Incorrect 75 ms 54636 KB Output isn't correct
25 Incorrect 163 ms 96528 KB Output isn't correct
26 Correct 361 ms 123992 KB Output is correct
27 Correct 513 ms 125188 KB Output is correct
28 Correct 611 ms 110328 KB Output is correct
29 Correct 605 ms 111036 KB Output is correct
30 Correct 561 ms 115224 KB Output is correct
31 Correct 432 ms 62244 KB Output is correct
32 Correct 443 ms 114624 KB Output is correct