oj.uz

Submission #1094368

# Submission time Handle Problem Language Result Execution time Memory
1094368 2024-09-29T12:57:11 Z Rafat Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 743 ms 135592 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <time.h>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>

using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>

using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// to erase in multiset-> less_equal<T> and 
// s.erase(s.find_by_order(s.order_of_key(x)))
// lower_bound(x)=>(cannot use the stl lower_bound function)
// ll idx = s.order_of_key(x)
// if(idx == s.size()) -> no lower_bound
// else lb = *s.find_by_order(idx) // as 0-indexing
// idx-1 will give highest value which is strictly less than x
// for upper_bound->do the same with (x+1)

typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef tuple<ll, ll, ll> t64;
typedef vector<t64> vt64;
typedef vector<vt64> vvt64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef vector<vector<p32> > vvp32;
typedef vector<bool> vb;
ll mod =  1e9+7, MOD = 998244353;
double eps = 1e-12;
// #define forn(i,e) for(ll i = 0; i < e; i++)
#define FOR(s, e, i) for(int i = s; i <= e; i++)
// #define rforn(i,s) for(ll i = s; i >= 0; i--)
#define ROF(s ,e, i) for(int i = s; i >= e; i--)
#define coutAll(A) for(auto asdafas : A) cout <<  asdafas << " "; cout << "\n";
#define foutAll(A) for(auto asdafas : A) fout <<  asdafas << " "; cout << "\n";
#define cinAll(A) for(auto &asdafas : A) cin >>  asdafas;
#define finAll(A) for(auto &asdafas : A) fin >>  asdafas;
#define minpq priority_queue<ll, v64, greater<ll>>
#define maxpq priority_queue<ll> 
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fi first
#define se second
ll inf = LLONG_MAX;
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> pii;
//#define MAXN 1000000

void solve(int it)
{
    int h, w;
    cin>> h >> w;
    vector<string>A(h);
    cinAll(A);
    vv32 dist(h, v32(w,1e9));
    dist[0][0] = 1;
    deque<p32>q;
    q.push_front({0, 0});
    v32 dx = {1, -1, 0, 0};
    v32 dy = {0, 0, 1, -1};
    while(!q.empty()){
        auto u = q.front();
        // cout << u.fi << " " << u.se << "\n";
        q.pop_front();
        FOR(0, 3, i){
            int x = u.fi+dx[i];
            int y = u.se+dy[i];
            if(x < 0) continue;
            if(y < 0) continue;
            if(x >= h) continue;
            if(y >= w) continue;
            if(A[x][y] == '.') continue;
            if(A[x][y] == A[u.fi][u.se]){
                // same, 0-edge
                if(dist[x][y] > dist[u.fi][u.se]){
                    dist[x][y] = dist[u.fi][u.se];
                    q.push_front({x, y});
                }
            }
            else{
                // 1-edge;
                if(dist[x][y] > dist[u.fi][u.se]+1){
                    dist[x][y] = dist[u.fi][u.se]+1;
                    q.push_back({x, y});
                }
            }
        }
    }
    int ans = 1;
    FOR(0, h - 1, i){
        FOR(0, w - 1, j){
            if(A[i][j] == '.') continue;
            ans = max(ans, dist[i][j]);
        }
    }
    cout << ans;

}


int main()
{
    // fast_cin();    
    ll t = 1;
    // cin >> t;
    for(int it=1; it<=t; it++)
    {
        //cout << "Case " << it << ": ";
        solve(it);
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2140 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 7 ms 1480 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 5 ms 860 KB Output is correct
13 Correct 3 ms 860 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 12 ms 2204 KB Output is correct
16 Correct 14 ms 2176 KB Output is correct
17 Correct 10 ms 1984 KB Output is correct
18 Correct 7 ms 1628 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 57 ms 10520 KB Output is correct
3 Correct 376 ms 108976 KB Output is correct
4 Correct 98 ms 25808 KB Output is correct
5 Correct 212 ms 55876 KB Output is correct
6 Correct 743 ms 122596 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 2 ms 856 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 54 ms 10460 KB Output is correct
14 Correct 30 ms 6488 KB Output is correct
15 Correct 23 ms 7260 KB Output is correct
16 Correct 24 ms 4188 KB Output is correct
17 Correct 132 ms 27836 KB Output is correct
18 Correct 85 ms 27472 KB Output is correct
19 Correct 100 ms 26000 KB Output is correct
20 Correct 82 ms 23892 KB Output is correct
21 Correct 201 ms 57684 KB Output is correct
22 Correct 196 ms 55892 KB Output is correct
23 Correct 256 ms 47696 KB Output is correct
24 Correct 192 ms 56660 KB Output is correct
25 Correct 339 ms 109260 KB Output is correct
26 Correct 403 ms 123748 KB Output is correct
27 Correct 554 ms 135592 KB Output is correct
28 Correct 712 ms 122644 KB Output is correct
29 Correct 686 ms 121036 KB Output is correct
30 Correct 609 ms 124632 KB Output is correct
31 Correct 568 ms 63060 KB Output is correct
32 Correct 511 ms 124428 KB Output is correct