Submission #895893

#	Time	Username	Problem	Language	Result	Execution time	Memory
895893		nosaboy	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	711 ms	185184 KiB

tracks

#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 / 30
• Subtask 2: 70 / 70