제출 #1286812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286812		samarthkulkarni	Mecho (IOI09_mecho)	C++20	6 / 100	550 ms	131072 KiB

mecho

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("fast-math")

#define ll int
#define ld long double
#define vi vector<ll>
#define endl "\n"
#define pr pair<ll, ll>
#define ff first 
#define ss second
#define all(x) x.begin(), x.end()
const int mod = 1e9+7;
void _p(ll a){cout<<a<<endl;}
void _p(string a){cout<<a<<endl;}
void _p(ld a) {cout<<a<<endl;}
template <class T>
void _p(vector<T> a){for(T val:a)cout<<val<<" ";cout<<endl;}
#define debug(x) cout<<#x<<" -> ";_p(x)

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;

vector<pr> move8 = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
vector<pr> move4 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<pr> move2 = {{0, 1}, {1, 0}};

void solution();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}

pr operator+(pr p1, pr p2) {
	pr ans = {p1.ff +p2.ff, p1.ss+p2.ss};
	return ans;
}


const int MAXN = 805;
const int inf = 1e9;
char A[MAXN][MAXN];
int arr[MAXN][MAXN];
ll n, s;
pr start, destination;
vector<pr> H;
bool vis[MAXN][MAXN];



bool correct(pr cords) {
	return cords.ff <= n && cords.ff >= 1 && 
		cords.ss <= n && cords.ss >= 1 &&
		A[cords.ff][cords.ss] != 'T';
}

void calculateArrival() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			arr[i][j] = inf;
		}
	}

	queue<pr> q;
	pr wa = {-1, -1};

	ll tm = 0;
	for (auto val : H) q.push(val);
	q.push(wa);

	while (!q.empty()) {
		pr e = q.front(); q.pop();

		if (e == wa) {
			if (q.size() > 0) q.push(wa);
			tm++;
			continue;
		}

		if (arr[e.ff][e.ss] < tm) continue;
		arr[e.ff][e.ss] = tm;

		for (auto D : move4) {
			pr nkw = D + e;
			if (!correct(nkw) || arr[nkw.ff][nkw.ss] != inf || 
				A[nkw.ff][nkw.ss] == 'D') continue;
			q.push(nkw);
		}
	}
}


// bool isValid(ll tm) {

// 	if (tm >= arr[start.ff][start.ss]) return false;
// 	queue<pair<pr, ll>> q;
// 	q.push({start, 0});


// 	while (!q.empty()) {
// 		auto [e, t] = q.front(); q.pop();

// 		if (vis[e.ff][e.ss] || 
// 			ceil((ld)t/s)+ tm > arr[e.ff][e.ss]) continue;
// 		vis[e.ff][e.ss] = true;



// 		if (e == destination) return true;

// 		for (auto D : move4) {
// 			pr nkw = e+D;
// 			if (!correct(nkw) || vis[nkw.ff][nkw.ss]) continue;
// 			q.push({nkw, t+1});
// 		}

// 	}


// 	return false;
// }

bool isValid(int waiting_time) {
    if (waiting_time >= arr[start.ff][start.ss]) {
        return false;
    }

    queue<pair<pr, int>> q;
    q.push({start, 0});
    vis[start.ff][start.ss] = true;

    while (!q.empty()) {
        auto [pos, steps] = q.front();
        q.pop();

        if (pos == destination) {
            return true;
        }

        for (auto D : move4) {
            pr next_pos = pos + D;
            int next_steps = steps + 1;
            
            if (!correct(next_pos) || vis[next_pos.ff][next_pos.ss]) {
                continue;
            }
            
            int mecho_arrival = waiting_time + (next_steps + s - 1) / s;
            
            // Mecho moves DURING the minute, bees arrive AT THE END
            // So if they're in the same minute, Mecho is safe
            if (mecho_arrival > arr[next_pos.ff][next_pos.ss]) {
                continue;
            }
            
            vis[next_pos.ff][next_pos.ss] = true;
            q.push({next_pos, next_steps});
        }
    }

    return false;
}


void solution() {
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= n; j++) {
    		cin >> A[i][j];
    		if (A[i][j] == 'M') start = {i, j};
    		if (A[i][j] == 'D') destination = {i, j};
    		if (A[i][j] == 'H') H.push_back({i, j});
    	}
    }


    calculateArrival();


    // {
    // 	for (int i = 1; i <= n; i++) {
    // 		for (int j = 1; j <= n; j++) {
    // 			cout << arr[i][j] << " ";
    // 		}
    // 		cout << endl;
    // 	}
    // }



    
    ll p = 0, q = 1e7;
    ll ans = -1;
    while (p <= q) {
    	ll mid = (p + q)/2;
    	if (isValid(mid)) {
    		ans = mid;
    		p = mid+1;
    	}else q = mid-1;


    	memset(vis, 0, sizeof(vis));
    }


    cout << ans << endl;


}

• Subtask 1: 6 / 100