제출 #986158

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986158		sarthakgangwal	Mecho (IOI09_mecho)	C++14	100 / 100	194 ms	26260 KiB

mecho

//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);}

    }
}

• Subtask 1: 100 / 100