oj.uz

Submission #988062

# Submission time Handle Problem Language Result Execution time Memory
988062 2024-05-24T02:47:42 Z sarthakgangwal Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 1603 ms 1048576 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);
        // ll mat[h+2][w+2]={0};
        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<bool>> vis(h+2, vb(w+2,0));
        ll ans=0;

        ll movx[4]={1,0,-1,0}, movy[4]={0,1,0,-1};
        vpll v,prev;
        prev.pb({1,1});

        function<void(ll,ll)> dfs = [&](ll x,ll y){
            if(vis[x][y]){return;}
            vis[x][y]=1;
            for(ll i=0;i<4;i++){
                ll xx=x+movx[i], yy=y+movy[i];
                if(mat[xx][yy]==0 || vis[xx][yy]){continue;}
                else if(mat[xx][yy]==mat[x][y]){dfs(xx,yy);}
                else{v.pb({xx,yy});}
            }
        };

        while(!prev.empty()){
            for(pll p:prev){dfs(p.ff,p.ss);}
            prev=v; v={};
            ans++;
        }

        CC(ans);

    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3180 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 9 ms 4052 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 3 ms 900 KB Output is correct
11 Correct 3 ms 1628 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 3 ms 1116 KB Output is correct
14 Correct 3 ms 1136 KB Output is correct
15 Correct 13 ms 2964 KB Output is correct
16 Correct 18 ms 3180 KB Output is correct
17 Correct 11 ms 2652 KB Output is correct
18 Correct 9 ms 4052 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1628 KB Output is correct
2 Correct 54 ms 13456 KB Output is correct
3 Correct 346 ms 129064 KB Output is correct
4 Correct 96 ms 31016 KB Output is correct
5 Correct 218 ms 73088 KB Output is correct
6 Correct 1029 ms 275032 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct
8 Correct 2 ms 1628 KB Output is correct
9 Correct 3 ms 1824 KB Output is correct
10 Correct 2 ms 1368 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 54 ms 13288 KB Output is correct
14 Correct 32 ms 8028 KB Output is correct
15 Correct 25 ms 8540 KB Output is correct
16 Correct 27 ms 5976 KB Output is correct
17 Correct 143 ms 33616 KB Output is correct
18 Correct 117 ms 32852 KB Output is correct
19 Correct 103 ms 30804 KB Output is correct
20 Correct 79 ms 28280 KB Output is correct
21 Correct 207 ms 75340 KB Output is correct
22 Correct 212 ms 73088 KB Output is correct
23 Correct 276 ms 63060 KB Output is correct
24 Correct 208 ms 73872 KB Output is correct
25 Correct 653 ms 129064 KB Output is correct
26 Runtime error 1064 ms 1048576 KB Execution killed with signal 9
27 Correct 1603 ms 998500 KB Output is correct
28 Correct 1083 ms 291432 KB Output is correct
29 Correct 1059 ms 343008 KB Output is correct
30 Correct 1189 ms 497336 KB Output is correct
31 Correct 722 ms 97984 KB Output is correct
32 Correct 1527 ms 925076 KB Output is correct