oj.uz

Submission #895893

# Submission time Handle Problem Language Result Execution time Memory
895893 2023-12-31T03:32:29 Z nosaboy Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 711 ms 185184 KB 
#include <bits/stdc++.h>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using orderedMultiset = tree<T ,null_type,std::less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
#define f first
#define s second
#define pb push_back
#define rep(i, a, b) for(int i = a; i < (b); ++i) 
#define all(x) (x).begin(), (x).end()
ll MOD = 998244353;
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

ll add(ll x, ll y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}  
 
ll mult(ll x, ll y)
{
    return (x * 1ll * y) % MOD;
}
ll lpow(ll x, ll y)
{
    if(y == 0){
        return 1;
    }
    ll z = 1;
    while(y)
    {
        if(y & 1) z = mult(z, x);
        x = mult(x, x);
        y >>= 1;
    }
    return z;
}

ll inv(ll x) {
	return lpow(x, MOD - 2);
}
ll qexp(ll a, ll b, ll m) {
    ll res = 1;
    while (b) {
        if (b % 2) res = res * a % m;
        a = a * a % m;
        b /= 2;
    }
    return res;
}
ll divide(ll x, ll y)
{
    return mult(x, inv(y));
}
long long gcd(long long int a, long long int b)
{
  if (b == 0)
    return a;
  return gcd(b, a % b);
}
 
// Function to return LCM of two numbers
long long lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;
}
//math
 
 
vector <ll> ar;
vector <ll> br;
void printDivisors(ll n)
{
    // Note that this loop runs till square root
    for (ll i=1; i<=sqrt(n); i++)
    {
        if (n%i == 0)
        {
            // If divisors are equal, print only one
            if (n/i == i){
                ar.pb(i);
            }
                
  
            else{
                ar.pb(i);
                ar.pb(n/i);
            } // Otherwise print both
                
               
        }
    }
}
void bprintDivisors(ll n)
{
    // Note that this loop runs till square root
    for (ll i=1; i<=sqrt(n); i++)
    {
        if (n%i == 0)
        {
            // If divisors are equal, print only one
            if (n/i == i){
                br.pb(i);
            }
                
  
            else{
                br.pb(i);
                br.pb(n/i);
            } // Otherwise print both
                
               
        }
    }
}
 

vector <ll> va[5];
const int MAX_PR = 5'000'000;
vi prime;
bitset<MAX_PR> isprime;
 
vi eratosthenesSieve(int lim) {
	isprime.set(); isprime[0] = isprime[1] = 0;
	for (int i = 4; i < lim; i += 2) isprime[i] = 0;
	for (int i = 3; i*i < lim; i += 2) if (isprime[i])
		for (int j = i*i; j < lim; j += i*2) isprime[j] = 0;
	vi pr;
	rep(i,2,lim) if (isprime[i]) pr.push_back(i);
	return pr;
}
 



vector<ll> fact, invf;
 
void precompute(int n) {
    fact.assign(n + 1, 1); 
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    invf.assign(n + 1, 1);
    invf[n] = qexp(fact[n], MOD - 2, MOD);
    for (int i = n - 1; i > 0; i--) invf[i] = invf[i + 1] * (i + 1) % MOD;
}
 
ll nCk(ll n,ll k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invf[k] % MOD * invf[n - k] % MOD;
    // return fact[n] * qexp(fact[k], MOD - 2, MOD) % MOD * qexp(fact[n - k], MOD - 2, MOD) % MOD;
}
 
struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }
 
	// get representive component (uses path compression)
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
 
	bool same_set(int a, int b) { return get(a) == get(b); }
 
	int size(int x) { return -e[get(x)]; }
 
	bool unite(int x, int y) {  // union by size
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x; return true;
	}
};

int vis[4005][4005]; int dist[4005][4005];
const int R_CHANGE[]{0, 1, 0, -1};
const int C_CHANGE[]{1, 0, -1, 0};
void solve(){
    int n,m;cin>>n>>m;
    char v[n][m];
    rep(i,0,n){
        rep(j,0,m){
            cin>>v[i][j];
        }
    }
    int ans = 0;
    // bfs shortest path
    dist[0][0]=1; // start from top left
    deque<pi> q; q.push_front({0,0});
    while(!q.empty()){
        pi a = q.front(); q.pop_front(); // access and pop most optimal element
        int x = a.first; int y = a.second;
        ans = max(ans,dist[x][y]); // MAX of shortest dist
        rep(i,0,4){
            int r = x+R_CHANGE[i]; int c = y+C_CHANGE[i]; // new coord
            if (r < 0 || r >= n || c < 0 || c >= m || v[r][c] == '.' || vis[r][c]){
                // we do not want to visit
                continue;
            }
            if(!vis[r][c]){
                vis[r][c]=true;
                if(v[x][y] == v[r][c]){ // same cc, weight = 0
                    q.push_front({r,c}); // push to front since weight = 0 more optimal dist than weight = 1
                    dist[r][c] = dist[x][y]; // change distance
                }
                else{ // weight = 1
                    q.push_back({r,c}); // push to back since dist + 1 less optimal than dist + 0
                    dist[r][c] = dist[x][y]+1; // change distance to dist + 1 since weight of edge = 1
                }
                
            }
        }
    }
    cout<<ans<<endl;
}   



int main(){
	auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t; t=1;
    
    while(t--){
        solve();
    }
  
    
		
 
    
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
   cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12120 KB Output is correct
2 Correct 1 ms 2408 KB Output is correct
3 Correct 1 ms 2780 KB Output is correct
4 Correct 7 ms 11612 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 3 ms 5724 KB Output is correct
11 Correct 2 ms 5724 KB Output is correct
12 Correct 5 ms 8284 KB Output is correct
13 Correct 3 ms 8280 KB Output is correct
14 Correct 3 ms 8284 KB Output is correct
15 Correct 10 ms 11848 KB Output is correct
16 Correct 11 ms 12120 KB Output is correct
17 Correct 9 ms 11864 KB Output is correct
18 Correct 7 ms 11612 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 77648 KB Output is correct
2 Correct 45 ms 32380 KB Output is correct
3 Correct 255 ms 135772 KB Output is correct
4 Correct 80 ms 60188 KB Output is correct
5 Correct 170 ms 97824 KB Output is correct
6 Correct 679 ms 171188 KB Output is correct
7 Correct 14 ms 78428 KB Output is correct
8 Correct 14 ms 77640 KB Output is correct
9 Correct 3 ms 2908 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 13 ms 77880 KB Output is correct
12 Correct 1 ms 5212 KB Output is correct
13 Correct 40 ms 32436 KB Output is correct
14 Correct 24 ms 22096 KB Output is correct
15 Correct 23 ms 26636 KB Output is correct
16 Correct 19 ms 11088 KB Output is correct
17 Correct 106 ms 57856 KB Output is correct
18 Correct 85 ms 64848 KB Output is correct
19 Correct 75 ms 59984 KB Output is correct
20 Correct 63 ms 51024 KB Output is correct
21 Correct 155 ms 98924 KB Output is correct
22 Correct 149 ms 97680 KB Output is correct
23 Correct 194 ms 82732 KB Output is correct
24 Correct 150 ms 95852 KB Output is correct
25 Correct 457 ms 157008 KB Output is correct
26 Correct 711 ms 185184 KB Output is correct
27 Correct 645 ms 182912 KB Output is correct
28 Correct 702 ms 171452 KB Output is correct
29 Correct 674 ms 168656 KB Output is correct
30 Correct 674 ms 172868 KB Output is correct
31 Correct 423 ms 122324 KB Output is correct
32 Correct 666 ms 177080 KB Output is correct