Submission #1268795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268795		shidou26	Mecho (IOI09_mecho)	C++20	34 / 100	142 ms	11592 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#define int long long  

bool M2;

#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "(" #x << " = " << x << ")"

template<typename T> bool maximize(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }else return false;
}
template<typename T> bool minimize(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }else return false;
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

const int N = 8e2 + 3;
const char TREE = 'T', GRASS = 'G', HONEY = 'M', HOME = 'D', HIVE = 'H';

int n, s;
char board[N][N];
pii st, ed;
vector<pii> hive;

void input() {
	cin >> n >> s;

	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			cin >> board[i][j];

			if(board[i][j] == HIVE)
				hive.emplace_back(i, j);

			if(board[i][j] == HONEY)
				st = {i, j};

			if(board[i][j] == HOME)
				ed = {i, j};
		}
	}
}

const int dx[] = {1, 0, -1, 0},
	 	  dy[] = {0, 1, 0, -1};

int bee[N][N], mecho[N][N];

bool check(int wait) {
	queue<pii> q;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			mecho[i][j] = 1e18;
		}
	}

	mecho[st.fi][st.se] = wait * s;
	q.push(st);

	while(!q.empty()) {
		int u, v; tie(u, v) = q.front(); q.pop();

		for(int i = 0; i < 4; i++) {
			int x = dx[i] + u, y = dy[i] + v;

			if(1 <= x && x <= n && 1 <= y && y <= n && board[x][y] != TREE && board[x][y] != HIVE) {
				int cost = mecho[u][v] + 1;

				if(cost < bee[x][y] * s) {
					if(minimize(mecho[x][y], cost)) {
						q.emplace(x, y);
					}
				}  
			}
		}
	}

	return mecho[ed.fi][ed.se] < 1e18;
}

void process() {
	queue<pii> q;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			bee[i][j] = 1e18;
		}
	}

	for(pii c : hive) {
		int x, y; tie(x, y) = c;
		bee[x][y] = 0;
		q.emplace(x, y);
	}

	while(!q.empty()) {
		int u, v; tie(u, v) = q.front(); q.pop();

		for(int i = 0; i < 4; i++) {
			int x = dx[i] + u, y = dy[i] + v;
			
			if(1 <= x && x <= n && 1 <= y && y <= n && board[x][y] != TREE && board[x][y] != HOME) {
				if(minimize(bee[x][y], bee[u][v] + 1)) {
					q.emplace(x, y);
				}
			}
		}
	}

    int l = 0, r = 1e9, result = -1;
    while(l <= r) {
    	int mid = (l + r) >> 1;
    	if(check(mid)) result = mid, l = mid + 1;
    	else r = mid - 1;
    }

    cout << result << endl;
}

bool M1;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define task "Date_A_Live"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    int testcase = 1; // cin >> testcase;
    for(int i = 1; i <= testcase; i++) {
        input();
        process();
    }

    cerr << "Time Elapsed: " << fixed << setprecision(3) << (1000. * clock() / CLOCKS_PER_SEC) << " MS" << endl;
    cerr << "Global Memory Usage: " << abs(&M2 - &M1) << " MB" << endl;

    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int32_t main()':
mecho.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 34 / 100