제출 #986158

#제출 시각아이디문제언어결과실행 시간메모리
986158sarthakgangwalMecho (IOI09_mecho)C++14
100 / 100
194 ms26260 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 :)-----------------------------------------*/ ll forest[802][802]; vector<vector<pll>> M_ini(802,vpll(802,{INF,INF})); vector<vector<pll>> M; ll mx,my; ll dx,dy; vpll bees; ll n,s; ll movy[4] = {-1,0,1,0}; ll movx[4] = {0,1,0,-1}; bool ok=0; void bfs1(){ queue<pll> q; for(pll p:bees){q.push(p);} while(!q.empty()){ pll top = q.front();q.pop(); ll x =top.ff, y=top.ss; for(int i=0;i<4;i++){ ll xx=x+movx[i],yy=y+movy[i]; if(forest[xx][yy]==-1){ forest[xx][yy]=1+forest[x][y]; q.push({xx,yy}); } } } return; } bool bfs2(ll st){ M=M_ini; if(forest[mx][my]<=st){return 0;} queue<pll> q; q.push({mx,my}); M[mx][my]={st,0}; while(!q.empty()){ pll top = q.front();q.pop(); ll x =top.ff, y=top.ss; ll tim=M[x][y].ff, stp=M[x][y].ss; for(int i=0;i<4;i++){ ll xx=x+movx[i],yy=y+movy[i]; if(xx==dx && yy==dy){ok=1;return 1;} if(M[xx][yy].ff==INF && forest[xx][yy]!=-2){ if(stp<s-1){M[xx][yy]={tim,stp+1};} else{M[xx][yy]={tim+1,0};} if(M[xx][yy].ff<forest[xx][yy]){ q.push({xx,yy}); } else{ M[xx][yy].ff=INF;M[xx][yy].ss=INF; } } } } return 0; } int main(){ fast { cin>>n>>s; char x; for(ll i=0;i<802;i++){ forest[0][i]=-2; forest[n+1][i]=-2; forest[801][i]=-2; forest[i][0]=-2; forest[i][n+1]=-2; forest[i][801]=-2; } for(ll i=1;i<=n;i++){ for(ll j=1;j<=n;j++){ cin>>x; if(x=='M'){mx=i;my=j;forest[i][j]=-1;} if(x=='G'){forest[i][j]=-1;} if(x=='H'){forest[i][j]=0;bees.pb({i,j});} if(x=='T'){forest[i][j]=-2;} if(x=='D'){forest[i][j]=-2;dx=i;dy=j;} } } bfs1(); // for(ll i=1;i<=n;i++){ // for(ll j=1;j<=n;j++){ // cout<<forest[i][j]<<sp; // } // cout<<endl; // } // cout<<endl; // bfs2(1); // for(ll i=1;i<=n;i++){ // for(ll j=1;j<=n;j++){ // cout<<M[i][j].ff<<sp; // } // cout<<endl; // } // cout<<endl; ll l=0,h=6400000; while(l<h){ // cout<<l<<sp<<h<<endl; ll m = (l+h)/2; if(m==l){if(bfs2(h)){l=h;}break;} if(bfs2(m)){l=m;} else{h=m-1;} } bfs2(l); if(!ok){CC(-1);} else{CC(l);} } }
#Verdict Execution timeMemoryGrader output
Fetching results...