oj.uz

Submission #389429

# Submission time Handle Problem Language Result Execution time Memory
389429 2021-04-14T04:36:12 Z arwaeystoamneg Mecho (IOI09_mecho) C++17
11 / 100
 211 ms 8948 KB 
// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
}

int n, m;
const int MAX = 805;
string a[MAX];
int dist[MAX][MAX];
int check(int i, int j)
{
	return i >= 0 && j >= 0 && i < n&& j < n&& a[i][j] != 'T';
}
struct T
{
	int d, extra;
	T next()
	{
		T t = (*this);
		t.extra--;
		if (t.extra == -1)
		{
			t.extra = m;
			t.d++;
		}
		return t;
	}
	bool operator<(const T& x)const
	{
		if (d == x.d)return extra > x.extra;
		return d < x.d;
	}
};
T best[MAX][MAX];
T init = { inf,0 };
pii start, finish;
int solve(int t)
{
	F0R(i, n)F0R(j, n)best[i][j] = init;
	if (t >= dist[start.f][start.s])return 0;
	best[start.f][start.s] = { t,m };
	deque<pii>todo = { {start.f,start.s} };
	while (sz(todo))
	{
		int i = todo.back().f, j = todo.back().s;
		todo.pop_back();
		F0R(k, 4)
		{
			int x = i + dx[k], y = j + dy[k];
			if (check(x, y))
			{
				T temp = best[i][j];
				temp = temp.next();
				if (dist[x][y] > temp.d && temp < best[x][y])
				{
					best[x][y] = temp;
					todo.push_front({ x,y });
				}
			}
		}
	}
	return best[finish.f][finish.s].d != inf;
}
int main()
{
	setIO("");
	cin >> n >> m;
	F0R(i, n)cin >> a[i];
	F0R(i, n)
	{
		F0R(j, n)
		{
			if (a[i][j] == 'M')start = { i,j };
			if (a[i][j] == 'D')finish = { i,j };
		}
	}
	F0R(i, n)F0R(j, n)dist[i][j] = inf;
	deque<pii> todo;
	F0R(i, n)F0R(j, n)if (a[i][j] == 'H')todo.pb({ i,j }), dist[i][j] = 0;
	while (sz(todo))
	{
		int i = todo.back().f, j = todo.back().s;
		todo.pop_back();
		F0R(k, 4)
		{
			int x = i + dx[k], y = j + dy[k];
			if (check(x, y) && a[x][y] != 'D' && dist[x][y] > dist[i][j] + 1)
			{
				dist[x][y] = dist[i][j] + 1;
				todo.push_front({ x,y });
			}
		}
	}
	if (!solve(0))
	{
		cout << -1 << endl;
		return 0;
	}
	int l = 0, r = 4 * n;
	while (l < r)
	{
		int m = (l + r + 1) / 2;
		if (solve(m))
		{
			l = m;
		}
		else
		{
			r = m - 1;
		}
	}
	cout << l << endl;
}

Compilation message

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

Subtask #1
11.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Incorrect 0 ms 332 KB Output isn't correct
3 Incorrect 0 ms 332 KB Output isn't correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 0 ms 332 KB Output isn't correct
7 Incorrect 128 ms 8644 KB Output isn't correct
8 Incorrect 1 ms 460 KB Output isn't correct
9 Correct 1 ms 460 KB Output is correct
10 Incorrect 1 ms 464 KB Output isn't correct
11 Incorrect 1 ms 460 KB Output isn't correct
12 Correct 1 ms 716 KB Output is correct
13 Correct 1 ms 720 KB Output is correct
14 Incorrect 1 ms 716 KB Output isn't correct
15 Incorrect 1 ms 460 KB Output isn't correct
16 Correct 1 ms 460 KB Output is correct
17 Incorrect 1 ms 460 KB Output isn't correct
18 Incorrect 1 ms 464 KB Output isn't correct
19 Incorrect 1 ms 460 KB Output isn't correct
20 Incorrect 1 ms 460 KB Output isn't correct
21 Incorrect 1 ms 588 KB Output isn't correct
22 Incorrect 1 ms 588 KB Output isn't correct
23 Incorrect 1 ms 716 KB Output isn't correct
24 Incorrect 1 ms 716 KB Output isn't correct
25 Incorrect 1 ms 716 KB Output isn't correct
26 Incorrect 2 ms 716 KB Output isn't correct
27 Incorrect 2 ms 844 KB Output isn't correct
28 Incorrect 2 ms 844 KB Output isn't correct
29 Incorrect 1 ms 844 KB Output isn't correct
30 Incorrect 1 ms 844 KB Output isn't correct
31 Incorrect 2 ms 844 KB Output isn't correct
32 Incorrect 1 ms 844 KB Output isn't correct
33 Incorrect 16 ms 3788 KB Output isn't correct
34 Incorrect 21 ms 3780 KB Output isn't correct
35 Correct 32 ms 3664 KB Output is correct
36 Incorrect 21 ms 4300 KB Output isn't correct
37 Incorrect 27 ms 4300 KB Output isn't correct
38 Correct 42 ms 4300 KB Output is correct
39 Incorrect 27 ms 4816 KB Output isn't correct
40 Incorrect 37 ms 4812 KB Output isn't correct
41 Correct 52 ms 4812 KB Output is correct
42 Incorrect 32 ms 5316 KB Output isn't correct
43 Incorrect 43 ms 5324 KB Output isn't correct
44 Correct 63 ms 5324 KB Output is correct
45 Incorrect 42 ms 5880 KB Output isn't correct
46 Incorrect 56 ms 5836 KB Output isn't correct
47 Correct 98 ms 5856 KB Output is correct
48 Incorrect 50 ms 6348 KB Output isn't correct
49 Incorrect 65 ms 6348 KB Output isn't correct
50 Correct 92 ms 6348 KB Output is correct
51 Incorrect 57 ms 6928 KB Output isn't correct
52 Incorrect 77 ms 6848 KB Output isn't correct
53 Correct 149 ms 6932 KB Output is correct
54 Incorrect 65 ms 7464 KB Output isn't correct
55 Incorrect 91 ms 7432 KB Output isn't correct
56 Correct 149 ms 7372 KB Output is correct
57 Incorrect 74 ms 8012 KB Output isn't correct
58 Incorrect 105 ms 8020 KB Output isn't correct
59 Correct 171 ms 8012 KB Output is correct
60 Incorrect 85 ms 8532 KB Output isn't correct
61 Incorrect 117 ms 8532 KB Output isn't correct
62 Correct 211 ms 8644 KB Output is correct
63 Incorrect 200 ms 8560 KB Output isn't correct
64 Correct 192 ms 8568 KB Output is correct
65 Incorrect 199 ms 8648 KB Output isn't correct
66 Incorrect 148 ms 8512 KB Output isn't correct
67 Incorrect 184 ms 8528 KB Output isn't correct
68 Incorrect 63 ms 8524 KB Output isn't correct
69 Correct 54 ms 8564 KB Output is correct
70 Incorrect 50 ms 8564 KB Output isn't correct
71 Incorrect 46 ms 8588 KB Output isn't correct
72 Correct 41 ms 8588 KB Output is correct
73 Correct 50 ms 8812 KB Output is correct
74 Correct 102 ms 8792 KB Output is correct
75 Incorrect 101 ms 8840 KB Output isn't correct
76 Incorrect 100 ms 8948 KB Output isn't correct
77 Incorrect 103 ms 8820 KB Output isn't correct
78 Incorrect 115 ms 8776 KB Output isn't correct
79 Correct 102 ms 8936 KB Output is correct
80 Incorrect 92 ms 8820 KB Output isn't correct
81 Incorrect 111 ms 8788 KB Output isn't correct
82 Incorrect 95 ms 8780 KB Output isn't correct
83 Incorrect 126 ms 8780 KB Output isn't correct
84 Correct 124 ms 8796 KB Output is correct
85 Incorrect 123 ms 8780 KB Output isn't correct
86 Incorrect 122 ms 8772 KB Output isn't correct
87 Correct 121 ms 8776 KB Output is correct
88 Incorrect 173 ms 8724 KB Output isn't correct
89 Correct 146 ms 8812 KB Output is correct
90 Correct 124 ms 8652 KB Output is correct
91 Correct 145 ms 8696 KB Output is correct
92 Incorrect 113 ms 8812 KB Output isn't correct