oj.uz

Submission #784317

# Submission time Handle Problem Language Result Execution time Memory
784317 2023-07-16T02:40:38 Z Anthony_Liu Mecho (IOI09_mecho) C++11
56 / 100
 827 ms 12536 KB 
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3, unroll-loops")
//#pragma GCC target("avx2, bmi, bmi2, lzcnt, popcnt")
#define f first
#define s second
#define ll long long
#define pb push_back 
#define pi pair <int,int>
#define vi vector <int>
#define size(x) (int)(x).size()
#define all(x) x.begin(), x.end()
void setIO(string name = "") {
	cin.tie(0)->sync_with_stdio(0);
	if (size(name)) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

int N, S;
pi mecho;
pi home;
	
char grid[801][801];
vector <pi> hives;

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

bool valid(pi v) {
	if (v.f < 0 || v.s < 0 || v.f >= N || v.s >= N) return false;
	if (grid[v.f][v.s] == 'T' || grid[v.f][v.s] == 'D' || grid[v.f][v.s] == 'H') return false;
	return true;
}

bool calc(int eat) {
	
	queue <pi> q;
	vector <vi> dist1(801, vi(801, INT_MAX)); //dist from hive
	vector <vi> dist2(801, vi(801, INT_MAX)); //dist from mecho
	
	//calc hive dist
	for (auto i : hives) {
		q.push(i);
		dist1[i.f][i.s] = 0;
	}
	
	while (!q.empty()) {
		pi u = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			pi v = {u.f + dx[i], u.s + dy[i]};
			if (!valid(v)) continue;
			
			if (dist1[v.f][v.s] > dist1[u.f][u.s] + 1) {
				dist1[v.f][v.s] = dist1[u.f][u.s] + 1;
				q.push(v);
			}
		}
	}
	
	//calc mecho dist
	q.push(mecho);
	dist2[mecho.f][mecho.s] = 0;
	if (dist1[mecho.f][mecho.s] <= eat) return false;
	
	while (!q.empty()) {
		pi u = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			pi v = {u.f + dx[i], u.s + dy[i]};
			if (!valid(v)) continue;
			
			if (dist2[v.f][v.s] > dist2[u.f][u.s] + 1) {
				int md = dist2[u.f][u.s] + 1;
				int bd = dist1[v.f][v.s] - eat;
				if (md / S >= bd) continue;
				
				dist2[v.f][v.s] = dist2[u.f][u.s] + 1;
				q.push(v);
			}
		}
	}
	
	for (int i = 0; i < 4; i++) 
	{
		int nx = home.f + dx[i], ny = home.s + dy[i];
		int md = dist2[nx][ny];
		int bd = dist1[nx][ny] - eat;
		if (md / S >= bd) continue;
		
		if (valid({nx, ny}) && dist2[nx][ny] != INT_MAX) 
			return true;
	}
	return false;
}

int main()
{
	setIO();
	cin >> N >> S;
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> grid[i][j];
			if (grid[i][j] == 'M') mecho = {i, j};
			else if (grid[i][j] == 'D') home = {i, j};
			else if (grid[i][j] == 'H') {
				hives.pb({i, j});
			}
		}
	}
	
	int l = 0, r = N * N;
	int ans = -1;
	
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (calc(m)) {
			ans = m;
			l = m + 1;
		}
		else r = m - 1;
	}
	
	cout << ans << '\n'; 
	return 0;
}

Compilation message

mecho.cpp: In function 'void setIO(std::string)':
mecho.cpp:16:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:17:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
56.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 10756 KB Execution killed with signal 11
2 Runtime error 8 ms 10676 KB Execution killed with signal 11
3 Runtime error 10 ms 10784 KB Execution killed with signal 11
4 Runtime error 9 ms 10680 KB Execution killed with signal 11
5 Correct 9 ms 5420 KB Output is correct
6 Correct 10 ms 5444 KB Output is correct
7 Correct 782 ms 6760 KB Output is correct
8 Correct 13 ms 5444 KB Output is correct
9 Correct 11 ms 5444 KB Output is correct
10 Correct 11 ms 5492 KB Output is correct
11 Correct 10 ms 5476 KB Output is correct
12 Runtime error 11 ms 10852 KB Execution killed with signal 11
13 Correct 6 ms 5452 KB Output is correct
14 Correct 7 ms 5448 KB Output is correct
15 Runtime error 8 ms 10740 KB Execution killed with signal 11
16 Correct 11 ms 5592 KB Output is correct
17 Runtime error 8 ms 10756 KB Execution killed with signal 11
18 Correct 13 ms 5460 KB Output is correct
19 Runtime error 9 ms 10740 KB Execution killed with signal 11
20 Correct 15 ms 5460 KB Output is correct
21 Runtime error 8 ms 10744 KB Execution killed with signal 11
22 Correct 16 ms 5504 KB Output is correct
23 Runtime error 10 ms 10868 KB Execution killed with signal 11
24 Correct 16 ms 5508 KB Output is correct
25 Runtime error 8 ms 10884 KB Execution killed with signal 11
26 Correct 16 ms 5508 KB Output is correct
27 Runtime error 11 ms 10884 KB Execution killed with signal 11
28 Correct 19 ms 5508 KB Output is correct
29 Runtime error 9 ms 10912 KB Execution killed with signal 11
30 Correct 18 ms 5516 KB Output is correct
31 Runtime error 9 ms 10884 KB Execution killed with signal 11
32 Correct 18 ms 5596 KB Output is correct
33 Runtime error 16 ms 11392 KB Execution killed with signal 11
34 Correct 80 ms 5836 KB Output is correct
35 Correct 126 ms 5784 KB Output is correct
36 Runtime error 21 ms 11552 KB Execution killed with signal 11
37 Correct 105 ms 5972 KB Output is correct
38 Correct 179 ms 5908 KB Output is correct
39 Runtime error 21 ms 11652 KB Execution killed with signal 11
40 Correct 118 ms 5996 KB Output is correct
41 Correct 236 ms 5972 KB Output is correct
42 Runtime error 24 ms 11720 KB Execution killed with signal 11
43 Correct 144 ms 6056 KB Output is correct
44 Correct 288 ms 6036 KB Output is correct
45 Runtime error 28 ms 11932 KB Execution killed with signal 11
46 Correct 170 ms 6276 KB Output is correct
47 Correct 354 ms 6136 KB Output is correct
48 Runtime error 32 ms 12028 KB Execution killed with signal 11
49 Correct 204 ms 6268 KB Output is correct
50 Correct 386 ms 6272 KB Output is correct
51 Runtime error 36 ms 12132 KB Execution killed with signal 11
52 Correct 234 ms 6340 KB Output is correct
53 Correct 501 ms 6348 KB Output is correct
54 Runtime error 39 ms 12332 KB Execution killed with signal 11
55 Correct 285 ms 6440 KB Output is correct
56 Correct 562 ms 6436 KB Output is correct
57 Runtime error 46 ms 12476 KB Execution killed with signal 11
58 Correct 313 ms 6552 KB Output is correct
59 Correct 654 ms 6564 KB Output is correct
60 Runtime error 50 ms 12536 KB Execution killed with signal 11
61 Correct 339 ms 6648 KB Output is correct
62 Correct 748 ms 6660 KB Output is correct
63 Correct 667 ms 6684 KB Output is correct
64 Correct 827 ms 6652 KB Output is correct
65 Correct 740 ms 6696 KB Output is correct
66 Correct 696 ms 6652 KB Output is correct
67 Correct 692 ms 6680 KB Output is correct
68 Correct 603 ms 6684 KB Output is correct
69 Correct 638 ms 6676 KB Output is correct
70 Correct 607 ms 6680 KB Output is correct
71 Correct 629 ms 6676 KB Output is correct
72 Correct 604 ms 6684 KB Output is correct
73 Correct 676 ms 6952 KB Output is correct
74 Correct 721 ms 6948 KB Output is correct
75 Correct 787 ms 7064 KB Output is correct
76 Correct 722 ms 7040 KB Output is correct
77 Correct 733 ms 7080 KB Output is correct
78 Correct 746 ms 6960 KB Output is correct
79 Correct 703 ms 6912 KB Output is correct
80 Correct 729 ms 7000 KB Output is correct
81 Correct 742 ms 6912 KB Output is correct
82 Correct 714 ms 6912 KB Output is correct
83 Correct 757 ms 6988 KB Output is correct
84 Correct 737 ms 6880 KB Output is correct
85 Correct 781 ms 6872 KB Output is correct
86 Correct 746 ms 6876 KB Output is correct
87 Correct 738 ms 6876 KB Output is correct
88 Correct 784 ms 7072 KB Output is correct
89 Correct 769 ms 6916 KB Output is correct
90 Correct 768 ms 6816 KB Output is correct
91 Correct 764 ms 6840 KB Output is correct
92 Correct 816 ms 6912 KB Output is correct