Submission #624342

#	Time	Username	Problem	Language	Result	Execution time	Memory
624342		jackkkk	Mecho (IOI09_mecho)	C++11	4 / 100	219 ms	3336 KiB

mecho

// Mecho
// https://oj.uz/problem/view/IOI09_mecho

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <array>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <list>
#include <float.h>
#include <climits>
#include <cmath>

using namespace std;

void quit() {
    cout.flush();
    exit(0);
}
int n, s;
pair<int, int> st, dest;
bool tree[800][800]; //contains trees and grass. bee hives are also trees
bool tmp[800][800];
bool mecho_done[800][800];
deque<pair<int, int>> hives, mecho, tmp1, tmp2, new_hives, new_mecho;
pair<int, int> gto[4] = {{0,1}, {0,-1}, {-1,0}, {0,-1}};
bool in_grid(int a, int b){
    return a >= 0 && a < n && b >= 0 && b < n;
}
bool bee_can_go(int a, int b){
    return in_grid(a,b) && !(a == dest.first && b == dest.second) && !tree[a][b];
}
bool mecho_can_go(int a, int b){
    return in_grid(a, b) && !mecho_done[a][b] && !tree[a][b];
}
void bee_expand(){
    new_hives.clear();
    while(!hives.empty()){
        pair<int, int> curr = hives.front();
        int cx = curr.first, cy = curr.second;
        hives.pop_front();
        for(const auto &to : gto){
            int nx = to.first +cx, ny = to.second+cy;
            if(bee_can_go(nx, ny)){
                new_hives.emplace_back(nx, ny);
                tree[nx][ny]=1;
            }
        }
    }
    hives=new_hives;
}
bool finished;
bool mecho_expand(){
    //if can't expand anymore return false
    for(int i = 0; i < s; i++){
        new_mecho.clear();
        while(!mecho.empty()){
            pair<int, int> curr = mecho.front();
            int cx = curr.first, cy = curr.second;
            mecho.pop_front();
            for(const auto &to : gto){
                int nx = to.first +cx, ny = to.second+cy;
                if(mecho_can_go(nx, ny)){
                    new_mecho.emplace_back(nx, ny);
                    mecho_done[nx][ny]=1;                }
                if(nx == dest.first && ny == dest.second){
                    //can get to dest
                    finished=true;
                    return false;
                }
            }
        }
        mecho=new_mecho;
    }
    return mecho.size()>0;
}

bool good(int wait_time){
    tmp1 = hives;
    tmp2 = mecho;
    for(int i = 0; i < 800; i++){
        for(int j = 0; j < 800; j++){
            mecho_done[i][j]=0;
            tmp[i][j]=tree[i][j];
        }
    }
    mecho_done[st.first][st.second]=1;
    finished=false;

    //propogate until can't
    for(int i = 0; i < wait_time; i++){
        bee_expand();
    }

    while(mecho_expand()){
        bee_expand();
    }

    //reset variables
    for(int i = 0; i < 800; i++){
        for(int j = 0; j < 800; j++){
            tree[i][j]=tmp[i][j];
        }
    }
    hives=tmp1;
    mecho=tmp2;
    return finished;

}


int main(void){
    //freopen("qwer.in", "r", stdin);
    //freopen("qwer.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s;
    for(int i = 0; i < n; i++){
        string s; cin >> s;
        for(int j = 0; j < n; j++){
            if(s[j]=='T'){
                tree[i][j]=1;
            }
            else if(s[j]=='M'){
                st={i,j};
                mecho.emplace_back(i,j);
            }
            else if(s[j]=='D'){
                dest = {i,j};
            }
            else if(s[j] == 'H'){
                hives.emplace_back(i,j);
                tree[i][j]=1;
            }
        }
    }
    if(!good(0)){
        cout << "-1\n";
        quit();
    }
    int s = 0, e = 10000;
    while(s != e){
        int md = (s+e+1)/2;
        if(good(md)){
            s=md;
        }
        else{
            e=md-1;
        }
    }
    cout << s << "\n";
    quit();
}

• Subtask 1: 4 / 100