Submission #893264

#	Time	Username	Problem	Language	Result	Execution time	Memory
893264		Macker	Mecho (IOI09_mecho)	C++17	45 / 100	286 ms	1516 KiB

mecho

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define v(x) v[x.first][x.second]
#define bs(x) bs[x.first][x.second]

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")

int n, s;
vector<vector<bool>> mp;
vector<pii> hives;
pii strt;
pii trgt;

vector<pii> adj = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool in(pii x){
    if(x.first < 0 || x.first >= n) return 0;
    if(x.second < 0 || x.second >= n) return 0;
    return 1;
}

bool can(int t){
    vector<vector<bool>> v = mp;
    vector<vector<bool>> bs;
    bs.resize(n, vector<bool>(n));

    queue<pair<pii, int>> q, bq;
    q.push({strt, t});
    for(auto i : hives) bq.push({i, 0});
    while(bq.size() && bq.front().second < t){
        auto [a, d] = bq.front(); bq.pop();
        for (auto &&o : adj) {
            pii b = {a.first + o.first, a.second + o.second};
            if(in(b) && !v(b) && !bs(b)){
                bs(b) = true;
                bq.push({b, d + 1});
            }
        }
    }

    int nt = t;
    while(q.size()){
        nt += s;
        t++;
        while(q.size() && q.front().second < nt){
            auto [a, d] = q.front(); q.pop();
            if(bs(a)) continue;
            for (auto &&o : adj) {
                pii b = {a.first + o.first, a.second + o.second};
                if(in(b) && !v(b) && !bs(b)){
                    v(b) = true;
                    q.push({b, d + 1});
                }
                if(b == trgt) return true;
            }
        }
        while(bq.size() && bq.front().second < t){
        auto [a, d] = bq.front(); bq.pop();
            for (auto &&o : adj) {
                pii b = {a.first + o.first, a.second + o.second};
                if(in(b) && !v(b) && !bs(b)){
                    bs(b) = true;
                    bq.push({b, d + 1});
                }
            }
        }
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s;
    mp.resize(n, vector<bool>(n));
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0; j < n; j++) {
            char a = s[j];
            if(a == 'M') strt = {i, j};
            else if(a == 'D') { trgt = {i, j}; mp[i][j] = 1;}
            else if(a == 'H') hives.push_back({i, j});
            else if(a == 'T') mp[i][j] = 1;
        }
    }
    
    int l = 0, r = n * n, mid;
    while(l < r){
        mid = (l + r + 1) / 2;
        if(can(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
}

• Subtask 1: 45 / 100