# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
882618 |
2023-12-03T12:19:53 Z |
qrupafjzvm1 |
Mecho (IOI09_mecho) |
C++14 |
|
1000 ms |
65536 KB |
//memset 0x3f -> > 1000000000
#include <bits/stdc++.h>
#define f first
#define s second
#define MAXSIZE (int)(2e5+5)
// #define int long long
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef pair<int,int> ii;
string answerString[2] = {"NO", "YES"};
int add(int x, int y, int mod)
{
int t = x + y;
return t - mod * (t>=mod);
}
int sub(int x, int y, int mod)
{
int t = x - y;
return t + mod * (t<0);
}
int xd[4] = {0,0,1,-1}, yd[4] = {1,-1,0,0};
int d[808][808];
char c[808][808];
bool ch[808][808];
int mx, my, dx, dy, n, s;
vector <ii> hives;
void bfs()
{
queue <ii> q;
memset(d,0x3f,sizeof(d));
for (ii h : hives) {q.push(h); d[h.f][h.s] = 0;}
while (!q.empty())
{
ii u = q.front(); q.pop();
for (int i=0;i<4;i++)
{
ii v = {u.f + xd[i], u.s + yd[i]};
if (v.f>=1 && v.f<=n && v.s>=1 && v.s<=n
&& c[v.f][v.s] == 'G' && d[v.f][v.s]>d[u.f][u.s]+1)
{
d[v.f][v.s] = d[u.f][u.s] + 1;
q.push(v);
}
}
}
}
void dfs(ii u, int dt, int cnt)
{
ch[u.f][u.s] = true;
for (int i=0;i<4;i++)
{
ii v = {u.f + xd[i], u.s + yd[i]};
if (v.f>=1 && v.f<=n && v.s>=1 && v.s<=n
&& c[v.f][v.s] != 'T' && dt+(cnt==0)<d[v.f][v.s])
{
if (cnt==0) dfs(v,dt+1,s-1);
else dfs(v,dt,cnt-1);
}
}
}
signed main()
{
//freopen("mecho.inp","r",stdin);
//freopen("text.out","w",stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>s;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
cin>>c[i][j];
if (c[i][j]=='M') {mx = i, my = j;}
if (c[i][j]=='D') {dx = i, dy = j;}
if (c[i][j]=='H') hives.push_back({i,j});
}
bfs();
/*for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++) cout<<d[i][j]<<" ";
cout<<endl;
}*/
int l = -1, r = n*n+1, ans = -1;
while (r-l>1)
{
//cout<<l<<" "<<r<<endl;
memset(ch,0,sizeof(ch));
int m = (l + r) / 2; dfs({mx, my}, m, s);
if (ch[dx][dy]) l = ans = m;
else r = m;
}
memset(ch,0,sizeof(ch));
dfs({mx, my}, l, s);
if (ch[dx][dy]) cout<<l;
else cout<<-1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
4188 KB |
Output isn't correct |
2 |
Incorrect |
2 ms |
4188 KB |
Output isn't correct |
3 |
Incorrect |
1 ms |
4188 KB |
Output isn't correct |
4 |
Incorrect |
1 ms |
4188 KB |
Output isn't correct |
5 |
Runtime error |
44 ms |
65536 KB |
Execution killed with signal 9 |
6 |
Execution timed out |
1059 ms |
4184 KB |
Time limit exceeded |
7 |
Execution timed out |
1062 ms |
4700 KB |
Time limit exceeded |
8 |
Incorrect |
1 ms |
4188 KB |
Output isn't correct |
9 |
Execution timed out |
1085 ms |
4188 KB |
Time limit exceeded |
10 |
Correct |
92 ms |
4440 KB |
Output is correct |
11 |
Correct |
224 ms |
4268 KB |
Output is correct |
12 |
Runtime error |
37 ms |
65536 KB |
Execution killed with signal 9 |
13 |
Execution timed out |
1043 ms |
4188 KB |
Time limit exceeded |
14 |
Execution timed out |
1058 ms |
4188 KB |
Time limit exceeded |
15 |
Execution timed out |
1050 ms |
4188 KB |
Time limit exceeded |
16 |
Execution timed out |
1020 ms |
4184 KB |
Time limit exceeded |
17 |
Execution timed out |
1099 ms |
4184 KB |
Time limit exceeded |
18 |
Execution timed out |
1061 ms |
4188 KB |
Time limit exceeded |
19 |
Execution timed out |
1049 ms |
4188 KB |
Time limit exceeded |
20 |
Execution timed out |
1032 ms |
4188 KB |
Time limit exceeded |
21 |
Execution timed out |
1057 ms |
4188 KB |
Time limit exceeded |
22 |
Execution timed out |
1035 ms |
4188 KB |
Time limit exceeded |
23 |
Execution timed out |
1038 ms |
4188 KB |
Time limit exceeded |
24 |
Execution timed out |
1049 ms |
4696 KB |
Time limit exceeded |
25 |
Execution timed out |
1061 ms |
4280 KB |
Time limit exceeded |
26 |
Execution timed out |
1035 ms |
4184 KB |
Time limit exceeded |
27 |
Execution timed out |
1037 ms |
4184 KB |
Time limit exceeded |
28 |
Execution timed out |
1071 ms |
4188 KB |
Time limit exceeded |
29 |
Execution timed out |
1071 ms |
4188 KB |
Time limit exceeded |
30 |
Execution timed out |
1044 ms |
5724 KB |
Time limit exceeded |
31 |
Execution timed out |
1045 ms |
4188 KB |
Time limit exceeded |
32 |
Execution timed out |
1061 ms |
5980 KB |
Time limit exceeded |
33 |
Execution timed out |
1057 ms |
4188 KB |
Time limit exceeded |
34 |
Runtime error |
62 ms |
65536 KB |
Execution killed with signal 9 |
35 |
Execution timed out |
1030 ms |
15448 KB |
Time limit exceeded |
36 |
Execution timed out |
1081 ms |
4428 KB |
Time limit exceeded |
37 |
Execution timed out |
1069 ms |
4444 KB |
Time limit exceeded |
38 |
Execution timed out |
1088 ms |
18052 KB |
Time limit exceeded |
39 |
Execution timed out |
1084 ms |
4324 KB |
Time limit exceeded |
40 |
Runtime error |
47 ms |
65536 KB |
Execution killed with signal 9 |
41 |
Execution timed out |
1010 ms |
21084 KB |
Time limit exceeded |
42 |
Execution timed out |
1037 ms |
4440 KB |
Time limit exceeded |
43 |
Execution timed out |
1079 ms |
4552 KB |
Time limit exceeded |
44 |
Execution timed out |
1089 ms |
24012 KB |
Time limit exceeded |
45 |
Execution timed out |
1084 ms |
4424 KB |
Time limit exceeded |
46 |
Runtime error |
47 ms |
65536 KB |
Execution killed with signal 9 |
47 |
Execution timed out |
1093 ms |
33500 KB |
Time limit exceeded |
48 |
Execution timed out |
1061 ms |
4444 KB |
Time limit exceeded |
49 |
Execution timed out |
1060 ms |
4700 KB |
Time limit exceeded |
50 |
Execution timed out |
1061 ms |
38492 KB |
Time limit exceeded |
51 |
Execution timed out |
1045 ms |
4700 KB |
Time limit exceeded |
52 |
Runtime error |
48 ms |
65536 KB |
Execution killed with signal 9 |
53 |
Execution timed out |
1080 ms |
43600 KB |
Time limit exceeded |
54 |
Execution timed out |
1027 ms |
4696 KB |
Time limit exceeded |
55 |
Execution timed out |
1039 ms |
4700 KB |
Time limit exceeded |
56 |
Execution timed out |
1041 ms |
48996 KB |
Time limit exceeded |
57 |
Execution timed out |
1025 ms |
4648 KB |
Time limit exceeded |
58 |
Runtime error |
47 ms |
65536 KB |
Execution killed with signal 9 |
59 |
Execution timed out |
1033 ms |
54608 KB |
Time limit exceeded |
60 |
Execution timed out |
1053 ms |
4700 KB |
Time limit exceeded |
61 |
Execution timed out |
1043 ms |
4952 KB |
Time limit exceeded |
62 |
Execution timed out |
1059 ms |
60092 KB |
Time limit exceeded |
63 |
Execution timed out |
1022 ms |
4696 KB |
Time limit exceeded |
64 |
Execution timed out |
1068 ms |
9820 KB |
Time limit exceeded |
65 |
Execution timed out |
1027 ms |
4616 KB |
Time limit exceeded |
66 |
Execution timed out |
1044 ms |
4872 KB |
Time limit exceeded |
67 |
Execution timed out |
1035 ms |
4688 KB |
Time limit exceeded |
68 |
Execution timed out |
1050 ms |
5060 KB |
Time limit exceeded |
69 |
Execution timed out |
1071 ms |
7252 KB |
Time limit exceeded |
70 |
Execution timed out |
1014 ms |
4952 KB |
Time limit exceeded |
71 |
Execution timed out |
1054 ms |
4948 KB |
Time limit exceeded |
72 |
Runtime error |
59 ms |
65536 KB |
Execution killed with signal 9 |
73 |
Execution timed out |
1062 ms |
4956 KB |
Time limit exceeded |
74 |
Execution timed out |
1022 ms |
8792 KB |
Time limit exceeded |
75 |
Execution timed out |
1081 ms |
5164 KB |
Time limit exceeded |
76 |
Execution timed out |
1018 ms |
4908 KB |
Time limit exceeded |
77 |
Execution timed out |
1022 ms |
5248 KB |
Time limit exceeded |
78 |
Execution timed out |
1068 ms |
4956 KB |
Time limit exceeded |
79 |
Execution timed out |
1059 ms |
8796 KB |
Time limit exceeded |
80 |
Execution timed out |
1063 ms |
4900 KB |
Time limit exceeded |
81 |
Execution timed out |
1046 ms |
4956 KB |
Time limit exceeded |
82 |
Execution timed out |
1088 ms |
5248 KB |
Time limit exceeded |
83 |
Execution timed out |
1061 ms |
4948 KB |
Time limit exceeded |
84 |
Execution timed out |
1022 ms |
9612 KB |
Time limit exceeded |
85 |
Execution timed out |
1032 ms |
4956 KB |
Time limit exceeded |
86 |
Execution timed out |
1040 ms |
5200 KB |
Time limit exceeded |
87 |
Execution timed out |
1068 ms |
5212 KB |
Time limit exceeded |
88 |
Execution timed out |
1036 ms |
4944 KB |
Time limit exceeded |
89 |
Execution timed out |
1014 ms |
10932 KB |
Time limit exceeded |
90 |
Execution timed out |
1033 ms |
5204 KB |
Time limit exceeded |
91 |
Execution timed out |
1026 ms |
5468 KB |
Time limit exceeded |
92 |
Execution timed out |
1069 ms |
5052 KB |
Time limit exceeded |