oj.uz

Submission #988073

# Submission time Handle Problem Language Result Execution time Memory
988073 2024-05-24T03:08:51 Z sarthakgangwal Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 961 ms 336288 KB 
//This code is written by sarthakgangwal
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define tc int t;cin>>t;while(t--)
#define el "/n"
#define sp ' '
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define vvll vector<vector<long long int>>
#define vvpll vector<vector<pair<long long int, long long int>>>
#define vpll vector<pair<long long int,long long int>>
#define vb vector<bool>
#define pb push_back
#define pll pair<long long int,long long int>
#define ff first
#define ss second
#define I(x) ll x;cin>>x
#define CC(x) cout << (x) << endl
#define mod 1000000007
#define PI 3.14159265
long long INF = 2e18;
#define vll_in(v,n) for(ll i=0;i<=n-1;i++){ ll x;cin>>x; v.push_back(x);}
#define vvll_in(mat,r,c) for(ll i=0;i<=r-1;i++){ vector<ll> v;for(ll j=0;j<=c-1;j++){ll x;cin>>x;v.push_back(x);};mat.push_back(v);}
void print(bool k){cout << (k ? "YES" : "NO") <<"\n";}
void print(vll k,string sep = " ",string endline = "\n") {for (ll &i : k) cout << i << sep; cout << endline;}
#define all(x) (x).begin(), (x).end()

/*-------------------------------------Imp Concepts---------------------------------------------->
48-57 -> 0-9
65-90 -> A-Z
97-122 -> a-z
(a +-* b) mod M = ((a mod M) +-* (b mod M)) mod M.

use ordered set using oset<ll> , 2 extra functions
.order_of_key(k) gives number of items strictly smaller than k
.find_by_order(k) gives iterator to kth element in set 0 indexing
rest all functionalities are same as stl set like lowerbound upperbound erase find etc

use ordered multiset using oset<pll>
search upper_bound({val,-1})
insert insert({val,index}) index used so same val can be inserted uniquely
delete .erase( .upper_bound({val,-1}))
-----------------------------CODE BEGIN :)-----------------------------------------*/

//https://oj.uz/problem/view/BOI13_tracks
int main(){
    fast
    {
        I(h);I(w);
        vvll mat(h+2,vll(w+2,0));

        for(ll i=1;i<=h;i++){
            for(ll j=1;j<=w;j++){
                char x;cin>>x;
                if(x=='F'){mat[i][j]=1;}
                if(x=='R'){mat[i][j]=2;}   
            }
        }

        vector<vector<ll>> vis(h+2, vll(w+2,0));
        ll ans=0;

        ll movx[4]={1,0,-1,0}, movy[4]={0,1,0,-1};
        vis[1][1]=1;
        deque<pll> dq; dq.push_front({1,1});

        while(!dq.empty()){
            pll T = dq.front(); dq.pop_front();
            ll x=T.ff, y=T.ss;
            ans=vis[x][y];
            for(ll i=0;i<4;i++){
                ll xx=x+movx[i], yy=y+movy[i];
                if(mat[xx][yy]==0 || vis[xx][yy]!=0){continue;}
                else if(mat[xx][yy]==mat[x][y]){dq.push_front({xx,yy});vis[xx][yy]=vis[x][y];}
                else{dq.pb({xx,yy});vis[xx][yy]=vis[x][y]+1;}
            }
        }

        CC(ans);

    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4444 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 7 ms 3420 KB Output is correct
5 Correct 3 ms 1884 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 3 ms 1372 KB Output is correct
11 Correct 2 ms 1236 KB Output is correct
12 Correct 6 ms 1880 KB Output is correct
13 Correct 3 ms 1884 KB Output is correct
14 Correct 3 ms 1880 KB Output is correct
15 Correct 11 ms 4700 KB Output is correct
16 Correct 13 ms 4656 KB Output is correct
17 Correct 10 ms 4444 KB Output is correct
18 Correct 7 ms 3420 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1628 KB Output is correct
2 Correct 66 ms 26460 KB Output is correct
3 Correct 389 ms 267364 KB Output is correct
4 Correct 128 ms 63192 KB Output is correct
5 Correct 204 ms 150612 KB Output is correct
6 Correct 822 ms 294952 KB Output is correct
7 Correct 3 ms 1372 KB Output is correct
8 Correct 2 ms 1628 KB Output is correct
9 Correct 3 ms 1372 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct
11 Correct 2 ms 1624 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 69 ms 26460 KB Output is correct
14 Correct 42 ms 15448 KB Output is correct
15 Correct 29 ms 16988 KB Output is correct
16 Correct 28 ms 11352 KB Output is correct
17 Correct 143 ms 68180 KB Output is correct
18 Correct 132 ms 67152 KB Output is correct
19 Correct 133 ms 62808 KB Output is correct
20 Correct 87 ms 57932 KB Output is correct
21 Correct 225 ms 155728 KB Output is correct
22 Correct 195 ms 150352 KB Output is correct
23 Correct 376 ms 129624 KB Output is correct
24 Correct 240 ms 152144 KB Output is correct
25 Correct 855 ms 267148 KB Output is correct
26 Correct 495 ms 305044 KB Output is correct
27 Correct 739 ms 336288 KB Output is correct
28 Correct 926 ms 295080 KB Output is correct
29 Correct 961 ms 290284 KB Output is correct
30 Correct 782 ms 299628 KB Output is correct
31 Correct 604 ms 172028 KB Output is correct
32 Correct 694 ms 315564 KB Output is correct