oj.uz

Submission #988069

# Submission time Handle Problem Language Result Execution time Memory
988069 2024-05-24T02:56:28 Z sarthakgangwal Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 1594 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]==1){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]==1){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 21 ms 3436 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 9 ms 4328 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 344 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 3 ms 1628 KB Output is correct
12 Correct 7 ms 1736 KB Output is correct
13 Correct 3 ms 1116 KB Output is correct
14 Correct 3 ms 1240 KB Output is correct
15 Correct 13 ms 3236 KB Output is correct
16 Correct 18 ms 3696 KB Output is correct
17 Correct 11 ms 2908 KB Output is correct
18 Correct 9 ms 4308 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 56 ms 14940 KB Output is correct
3 Correct 355 ms 144856 KB Output is correct
4 Correct 93 ms 34640 KB Output is correct
5 Correct 221 ms 81852 KB Output is correct
6 Correct 1059 ms 290468 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct
8 Correct 3 ms 1880 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct
11 Correct 3 ms 1628 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 70 ms 14824 KB Output is correct
14 Correct 37 ms 8796 KB Output is correct
15 Correct 38 ms 9712 KB Output is correct
16 Correct 28 ms 6492 KB Output is correct
17 Correct 157 ms 37604 KB Output is correct
18 Correct 122 ms 36944 KB Output is correct
19 Correct 100 ms 34680 KB Output is correct
20 Correct 85 ms 31840 KB Output is correct
21 Correct 212 ms 84684 KB Output is correct
22 Correct 220 ms 81720 KB Output is correct
23 Correct 279 ms 70740 KB Output is correct
24 Correct 200 ms 82752 KB Output is correct
25 Correct 652 ms 144596 KB Output is correct
26 Runtime error 1092 ms 1048576 KB Execution killed with signal 9
27 Correct 1594 ms 998664 KB Output is correct
28 Correct 1124 ms 290668 KB Output is correct
29 Correct 1104 ms 343972 KB Output is correct
30 Correct 1181 ms 497340 KB Output is correct
31 Correct 729 ms 97980 KB Output is correct
32 Correct 1550 ms 925220 KB Output is correct