oj.uz

Submission #853155

# Submission time Handle Problem Language Result Execution time Memory
853155 2023-09-23T13:45:53 Z shiv_213 Tracks in the Snow (BOI13_tracks) C++
100 / 100
 488 ms 236368 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4952 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 5 ms 4188 KB Output is correct
5 Correct 2 ms 2140 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1884 KB Output is correct
11 Correct 2 ms 1624 KB Output is correct
12 Correct 4 ms 2396 KB Output is correct
13 Correct 2 ms 2268 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 7 ms 4444 KB Output is correct
16 Correct 9 ms 4704 KB Output is correct
17 Correct 6 ms 4716 KB Output is correct
18 Correct 5 ms 4188 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16220 KB Output is correct
2 Correct 30 ms 15172 KB Output is correct
3 Correct 142 ms 93448 KB Output is correct
4 Correct 54 ms 43164 KB Output is correct
5 Correct 115 ms 69144 KB Output is correct
6 Correct 482 ms 186568 KB Output is correct
7 Correct 10 ms 16948 KB Output is correct
8 Correct 9 ms 16220 KB Output is correct
9 Correct 1 ms 988 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 8 ms 16732 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 29 ms 15160 KB Output is correct
14 Correct 16 ms 9812 KB Output is correct
15 Correct 17 ms 14308 KB Output is correct
16 Correct 14 ms 6488 KB Output is correct
17 Correct 71 ms 32784 KB Output is correct
18 Correct 66 ms 47832 KB Output is correct
19 Correct 54 ms 43092 KB Output is correct
20 Correct 35 ms 27280 KB Output is correct
21 Correct 85 ms 61104 KB Output is correct
22 Correct 116 ms 69240 KB Output is correct
23 Correct 154 ms 56272 KB Output is correct
24 Correct 91 ms 59384 KB Output is correct
25 Correct 404 ms 159136 KB Output is correct
26 Correct 277 ms 236368 KB Output is correct
27 Correct 344 ms 212292 KB Output is correct
28 Correct 461 ms 186280 KB Output is correct
29 Correct 488 ms 183212 KB Output is correct
30 Correct 423 ms 191564 KB Output is correct
31 Correct 341 ms 115404 KB Output is correct
32 Correct 345 ms 183684 KB Output is correct