Submission #1306694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306694		mudanvit	Mecho (IOI09_mecho)	C++20	84 / 100	149 ms	6952 KiB

mecho

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using pii = pair<int,int>;
int x[4] = {1,-1,0,0};
int y[4] = {0,0,1,-1};
int main() {
	int N, S; cin>>N>>S;
    int arr[N][N];
    unordered_map<char, int> lets;
    lets['T']=1; lets['G']=2;lets['M']=3; lets['D']=4, lets['H']=5;
    //G, M, D, H
    queue<pii> hives;
    pii start;
    pii end;
    int dist[N][N];
    bool visit[N][N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            visit[i][j] = false;
            dist[i][j] = -1;
        }
    }
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            char let; cin>>let;
            int num = lets[let];
            arr[i][j]=num;
            if (num==5){hives.push({i, j}); dist[i][j]=0;visit[i][j]=true;}
            if (num==3){start = {i, j};}
            if (num==4){end = {i, j};}
        }
    }
    while (!hives.empty()) {
        pii loc = hives.front();
        hives.pop();
        for (int i = 0; i < 4; i++) {
            int nf = loc.F + x[i];
            int ns = loc.S + y[i];
            if (nf < 0 || nf >= N || ns < 0 || ns >= N) {continue;}
            if (visit[nf][ns]||arr[nf][ns] == 1) {continue;}
            visit[nf][ns] = true;
            dist[nf][ns] = dist[loc.F][loc.S] + 1;
            hives.push({nf, ns});
        }
    }
    int min = -1;
    int max = dist[start.F][start.S];
    while (max>min+1){
        int mid = (max+min)/2;
        queue<std::pair<int, pii>> order;
        bool visit[N][N];
        for (int i=0; i<N; i++){for(int j = 0; j<N; j++){visit[i][j]=false;}}
        order.push({0, start});
        visit[start.F][start.S]=true;
        while (!order.empty()){
            pii loc = order.front().second;
            int distance = order.front().first;
            order.pop();
            for (int i=0; i<4; i++){
                int nf = loc.F + x[i];
                int ns = loc.S + y[i];
                if (nf < 0 || nf >= N || ns < 0 || ns >= N) {continue;}
                if (visit[nf][ns]||arr[nf][ns] == 1) {continue;}
                if ((distance+1)/S + mid >= dist[nf][ns]){continue;}
                visit[nf][ns] = true;
                order.push({distance + 1, {nf, ns}});
            }
        }
        if (visit[end.F][end.S]){min = mid;}
        else{max = mid;}
    }
    cout<<min<<endl;
}

• Subtask 1: 84 / 100