Submission #484548

# Submission time Handle Problem Language Result Execution time Memory
484548 2021-11-04T11:46:04 Z Sho10 Mecho (IOI09_mecho) C++17
46 / 100
293 ms 13692 KB
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
#define ll long long
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define aint(a) (a).begin(), (a).end()
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 998244353
#define PI 3.14159265359
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,s,sx,sy,dbees[805][805],d[805][805],viz[505][505],fx,fy;
pair<ll,ll>direction[5];
char a[805][805];
vector<pair<ll,ll>>hive;
ll check(ll x,ll y){
if(x>=1&&y>=1&&x<=n&&y<=n){
    return 1;
}else return 0;
}
ll verif(ll time){
for(ll i=1;i<=n;i++)
    for(ll j=1;j<=n;j++)
{
    d[i][j]=LINF;
    viz[i][j]=0;
}
queue<pair<ll,ll>>q;
d[sx][sy]=0;
viz[sx][sy]=1;
q.push(mp(sx,sy));
if(dbees[sx][sy]<=time){
q.pop();
}
while(!q.empty()){
    ll x,y;
    x=q.front().f;
    y=q.front().s;
    //cout<<x<<' '<<y<<endl;
    q.pop();
       for(ll i=0;i<4;i++)
    {
ll xx,yy;
xx=x+direction[i].f;
yy=y+direction[i].s;
if(a[xx][yy]=='T'||a[xx][yy]=='H'){
    continue;
}
if(check(xx,yy)==0){
    continue;
}
if(viz[xx][yy]==1){
        continue;
}
if((d[x][y]+1)/s>=dbees[xx][yy]-time){
    continue;
}
viz[xx][yy]=1;
d[xx][yy]=d[x][y]+1;
q.push(mp(xx,yy));
    }
}
ll ans=0;
for(ll i=0;i<4;i++)
{
    ll x=fx+direction[i].f,y=fy+direction[i].s;
    if(check(x,y)==0){
        continue;
    }
    if(viz[x][y]==0){
        continue;
    }
    if((d[x][y]/s)<dbees[x][y]-time){
        ans=1;
    }

}
return ans;
}
int32_t main(){
//CODE_START;
direction[0]=mp(-1,0);
direction[1]=mp(1,0);
direction[2]=mp(0,-1);
direction[3]=mp(0,1);
cin>>n>>s;
for(ll i=1;i<=n;i++)
{
    for(ll j=1;j<=n;j++)
    {
        cin>>a[i][j];
        if(a[i][j]=='M'){
            sx=i;
            sy=j;
        }else if(a[i][j]=='H'){
        hive.pb(mp(i,j));
    }else if(a[i][j]=='D'){
    fx=i;
    fy=j;
    }
}
}
for(ll i=1;i<=n;i++)
{
    for(ll j=1;j<=n;j++)
    {
        dbees[i][j]=LINF;
    }
}
queue<pair<ll,ll>>q;
for(auto it : hive){
    q.push(it);
    dbees[it.f][it.s]=0;
}
while(!q.empty()){
    ll x,y;
    x=q.front().f;
    y=q.front().s;
    q.pop();
    for(ll i=0;i<4;i++)
    {
ll xx,yy;
xx=x+direction[i].f;
yy=y+direction[i].s;
if(a[xx][yy]=='T'||a[xx][yy]=='D'||a[xx][yy]=='H'){
    continue;
}
if(check(xx,yy)&&viz[xx][yy]==0){
    viz[xx][yy]=1;
    q.push(mp(xx,yy));
    dbees[xx][yy]=dbees[x][y]+1;
}
    }
}
ll l=1,r=n*n,ans=0;
//cout<<"DA"<<endl;
while(l<=r){
    ll mid=(l+r)/2;
  //  cout<<mid<<endl;
    if(verif(mid)){
        l=mid+1;
        ans=mid;
    }else {
    r=mid-1;
}
}
cout<<ans<<endl;
}


# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Incorrect 110 ms 13068 KB Output isn't correct
8 Incorrect 0 ms 460 KB Output isn't correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 0 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 1100 KB Output is correct
13 Correct 1 ms 972 KB Output is correct
14 Incorrect 1 ms 1136 KB Output isn't correct
15 Correct 0 ms 588 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 716 KB Output is correct
20 Correct 1 ms 716 KB Output is correct
21 Correct 1 ms 844 KB Output is correct
22 Correct 1 ms 844 KB Output is correct
23 Correct 1 ms 972 KB Output is correct
24 Correct 1 ms 972 KB Output is correct
25 Correct 1 ms 1100 KB Output is correct
26 Correct 1 ms 1124 KB Output is correct
27 Correct 1 ms 1100 KB Output is correct
28 Correct 2 ms 1100 KB Output is correct
29 Correct 1 ms 1228 KB Output is correct
30 Correct 1 ms 1228 KB Output is correct
31 Correct 1 ms 1356 KB Output is correct
32 Correct 1 ms 1228 KB Output is correct
33 Correct 12 ms 6380 KB Output is correct
34 Correct 15 ms 6348 KB Output is correct
35 Correct 25 ms 6348 KB Output is correct
36 Correct 15 ms 7140 KB Output is correct
37 Correct 16 ms 7152 KB Output is correct
38 Correct 31 ms 7264 KB Output is correct
39 Correct 18 ms 8056 KB Output is correct
40 Correct 19 ms 8012 KB Output is correct
41 Correct 45 ms 8012 KB Output is correct
42 Correct 24 ms 8908 KB Output is correct
43 Correct 24 ms 8940 KB Output is correct
44 Correct 59 ms 8900 KB Output is correct
45 Incorrect 25 ms 9592 KB Output isn't correct
46 Incorrect 51 ms 9548 KB Output isn't correct
47 Incorrect 39 ms 9668 KB Output isn't correct
48 Incorrect 28 ms 10208 KB Output isn't correct
49 Incorrect 57 ms 10260 KB Output isn't correct
50 Incorrect 46 ms 10308 KB Output isn't correct
51 Incorrect 36 ms 10968 KB Output isn't correct
52 Incorrect 70 ms 10944 KB Output isn't correct
53 Incorrect 46 ms 10912 KB Output isn't correct
54 Incorrect 37 ms 11588 KB Output isn't correct
55 Incorrect 77 ms 11556 KB Output isn't correct
56 Incorrect 57 ms 11596 KB Output isn't correct
57 Incorrect 49 ms 12316 KB Output isn't correct
58 Incorrect 104 ms 12288 KB Output isn't correct
59 Incorrect 69 ms 12232 KB Output isn't correct
60 Incorrect 48 ms 12976 KB Output isn't correct
61 Incorrect 100 ms 12912 KB Output isn't correct
62 Incorrect 76 ms 13020 KB Output isn't correct
63 Incorrect 91 ms 13140 KB Output isn't correct
64 Incorrect 293 ms 12900 KB Output isn't correct
65 Incorrect 234 ms 12928 KB Output isn't correct
66 Incorrect 126 ms 13012 KB Output isn't correct
67 Incorrect 252 ms 12996 KB Output isn't correct
68 Incorrect 67 ms 12984 KB Output isn't correct
69 Correct 69 ms 12964 KB Output is correct
70 Correct 74 ms 12972 KB Output is correct
71 Correct 68 ms 12976 KB Output is correct
72 Incorrect 83 ms 12996 KB Output isn't correct
73 Correct 89 ms 13508 KB Output is correct
74 Incorrect 152 ms 13612 KB Output isn't correct
75 Incorrect 154 ms 13608 KB Output isn't correct
76 Incorrect 174 ms 13692 KB Output isn't correct
77 Incorrect 156 ms 13508 KB Output isn't correct
78 Incorrect 92 ms 13380 KB Output isn't correct
79 Incorrect 105 ms 13352 KB Output isn't correct
80 Incorrect 94 ms 13380 KB Output isn't correct
81 Incorrect 87 ms 13304 KB Output isn't correct
82 Incorrect 116 ms 13424 KB Output isn't correct
83 Incorrect 123 ms 13240 KB Output isn't correct
84 Incorrect 116 ms 13344 KB Output isn't correct
85 Incorrect 93 ms 13344 KB Output isn't correct
86 Incorrect 120 ms 13472 KB Output isn't correct
87 Incorrect 146 ms 13344 KB Output isn't correct
88 Incorrect 177 ms 13276 KB Output isn't correct
89 Incorrect 105 ms 13172 KB Output isn't correct
90 Incorrect 111 ms 13288 KB Output isn't correct
91 Incorrect 132 ms 13272 KB Output isn't correct
92 Incorrect 171 ms 13252 KB Output isn't correct