제출 #988062

#제출 시각아이디문제언어결과실행 시간메모리
988062sarthakgangwalTracks in the Snow (BOI13_tracks)C++17
97.81 / 100
1603 ms1048576 KiB
//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); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...