제출 #988062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
988062		sarthakgangwal	Tracks in the Snow (BOI13_tracks)	C++17	97.81 / 100	1603 ms	1048576 KiB

tracks

//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 / 30
• Subtask 2: 67.8125 / 70