Submission #895893

#TimeUsernameProblemLanguageResultExecution timeMemory
895893nosaboyTracks in the Snow (BOI13_tracks)C++17
100 / 100
711 ms185184 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...