oj.uz

Submission #585164

# Submission time Handle Problem Language Result Execution time Memory
585164 2022-06-28T11:21:25 Z darshitjn Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 675 ms 235836 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> // Common file
//#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
//using namespace __gnu_pbds;
#define gc getchar_unlocked
#define fo(i,n) for(ll i=0;i<n;i++)
#define Fo(i,k,n) for(ll i=k;i<n;i++)
#define ll long long
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%I64d",&x)
#define ss(s)	scanf("%s",s)
#define pb push_back
#define F first
#define S second
#define clr(x) memset(x, 0, sizeof(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define all(x) x.begin(), x.end()
#define PI 3.1415926535897932384626
#define deb(x) cout << #x << " " << x << "\n";
#define INP(v) for(auto &x:v){cin >> x;}
#define OUT(v) for(auto &x:v){cout << x << " ";}
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pll>		vpll;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
const ll mod = 1000000007;
const ll N = 2e5;
const ll Fact_Length = 5e5 + 100;
//template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;

// A.find_by_order(k-1) // gives kth smallest element
// A.order_of_key(x) // no. of elements which are less than x

//Takes a&b as input and Returns : The power (a,b), (a^b)%mod
/*ll Power(ll base, ll expo)
{
   ll $result=1; base%=mod;
   while(expo) {   if(expo%2==1)  $result=($result*base)%mod;     base=(base*base)%mod;     expo/=2; }
   return $result;
}
 
// It give the modulo inverse of a, (1/a)%mod
ll Mod_Inv(ll $a) { return Power($a,mod-2); }
 
ll Factorial[Fact_Length];
// It make the above Factorial[i] = i! array
ll Make_Factorial()
{
   Factorial[0]=1;
   for(ll i=1;i<Fact_Length;i++) { Factorial[i]=(i*Factorial[i-1])%mod; } return 0;
}
ll Implement_Make_Factorial=Make_Factorial();      //To Implement Make_Factorial
 
// Takes n&r as input and Returns : nCr%mod
ll nCr(ll $n,ll $r)
{
   if($n<$r || $n<0 || $r<0) return 0;
   //if($n>Fact_Length) { cout<<"Error"<<endl; return; }
   ll $ans=(Factorial[$n]*Mod_Inv(Factorial[$r]))%mod;
   $ans=($ans*Mod_Inv(Factorial[$n-$r]))%mod;
   return $ans;
}*/

/*void seive(ll n){           
    for(ll i=2; i*i<=n; i++){
        if(a[i]==0){
            for(ll j=i; i*j<=n; j++){
                a[i*j] = 1;
            }
        }
    }
}*/

/*ll pw(ll a,ll b){
    if(b==0)return 1;
    ll t=pw(a,b/2);
    if(b%2)return ((a*t*t)%mod);
    else return ((t*t)%mod);
}
*/
ll depth[4000][4000];
string snow[4000];
ll dx[] = {0,0,1,-1};
ll dy[] = {1,-1,0,0};
ll n,m;

bool valid(ll x,ll y){
    if(x<0 || x>n-1){return false;}
    if(y<0 || y>m-1){return false;}
    return (snow[x][y] != '.');
}

void solve(){
    cin >> n >> m;
    fo(i,n){
        cin >> snow[i];
    }
    deque <pll> q;
    q.pb({0,0});
    ll ans = 1;
    depth[0][0] = 1;
    while(!q.empty()){
        pll p = q.front();
        q.pop_front();
        ans = max(ans,depth[p.F][p.S]);
        fo(i,4){
            ll x = p.F+dx[i];
            ll y = p.S+dy[i];
            if(valid(x,y) && depth[x][y]==0){
                if(snow[x][y]==snow[p.F][p.S]){
                    q.push_front({x,y});
                    depth[x][y] = depth[p.F][p.S];
                }
                else{
                    q.push_back({x,y});
                    depth[x][y] = depth[p.F][p.S]+1;
                }
            }
        }
    }
    cout << ans << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    
    ll darshit = 1;
	//cin >> darshit;
    
    for(ll i=1;i<=darshit;i++)
    {
    //cout <<"Case #" << i <<": ";  
    solve();
    }


	return 0;
}

Compilation message

tracks.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4820 KB Output is correct
2 Correct 1 ms 452 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 6 ms 4180 KB Output is correct
5 Correct 2 ms 2260 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 708 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 3 ms 1748 KB Output is correct
11 Correct 2 ms 1748 KB Output is correct
12 Correct 5 ms 2516 KB Output is correct
13 Correct 3 ms 2204 KB Output is correct
14 Correct 3 ms 2256 KB Output is correct
15 Correct 9 ms 4440 KB Output is correct
16 Correct 11 ms 4820 KB Output is correct
17 Correct 8 ms 4564 KB Output is correct
18 Correct 6 ms 4308 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15876 KB Output is correct
2 Correct 35 ms 15068 KB Output is correct
3 Correct 188 ms 93324 KB Output is correct
4 Correct 60 ms 43060 KB Output is correct
5 Correct 122 ms 69352 KB Output is correct
6 Correct 562 ms 185292 KB Output is correct
7 Correct 9 ms 16724 KB Output is correct
8 Correct 10 ms 15948 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 9 ms 16340 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 36 ms 15056 KB Output is correct
14 Correct 22 ms 9952 KB Output is correct
15 Correct 17 ms 14264 KB Output is correct
16 Correct 18 ms 6604 KB Output is correct
17 Correct 87 ms 32928 KB Output is correct
18 Correct 63 ms 47612 KB Output is correct
19 Correct 61 ms 43148 KB Output is correct
20 Correct 45 ms 27180 KB Output is correct
21 Correct 109 ms 61020 KB Output is correct
22 Correct 114 ms 69244 KB Output is correct
23 Correct 164 ms 56320 KB Output is correct
24 Correct 97 ms 59244 KB Output is correct
25 Correct 434 ms 158832 KB Output is correct
26 Correct 675 ms 235836 KB Output is correct
27 Correct 520 ms 195564 KB Output is correct
28 Correct 654 ms 185372 KB Output is correct
29 Correct 592 ms 180824 KB Output is correct
30 Correct 637 ms 190348 KB Output is correct
31 Correct 464 ms 115388 KB Output is correct
32 Correct 581 ms 185880 KB Output is correct