oj.uz

답안 #554797

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
554797 2022-04-29T12:45:11 Z roctes7 Mecho (IOI09_mecho) C++17
24 / 100
 509 ms 31780 KB 
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define Endl "\n"
#define ENDL "\n"
#define fi first
#define se second
#define be  begin()
#define en  end()
#define pb push_back
#define mpa make_pair
typedef long long ll;
typedef long double ld;
const int MOD=1e9+7;
const int MAX=2e5+1;

ll n,s;
string arr[802][802];
bool vist[802][802];
ll mechoDist[802][802];
ll BeesDist[802][802];
pair<ll,ll> mecho;
pair<ll,ll> home;

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

bool valid (ll x,ll y){
return x>=1&&x<=n&&y>=1&&y<=n&&!vist[x][y]&&arr[x][y]!="T";
}


bool check =false;

void bfs (ll val){
vist[mecho.fi][mecho.se]=true;
queue<pair<ll,ll>>q;
q.push(mecho);

while (!q.empty()){
    auto p =q.front();
    ll x = p.fi;
    ll y = p.se;
    q.pop();
if(x==home.fi&&y==home.se)check=true;
for (int i=0;i<4;i++){
    if(home.fi+dx[i]==x&&home.se+dy[i]==y)check=true;
}

 if(val+mechoDist[x][y]>=BeesDist[x][y])continue;


for (ll i=0;i<4;i++){
        ll nx = x+dx[i];
        ll ny = y+dy[i];

        if(valid(nx,ny)){
          vist[nx][ny]=true;
          q.push(mpa(nx,ny));
        }
    }
}



}

int main(){

fastio
//freopen("11.in","r",stdin);
//freopen("cl.out","w",stdout);

cin>>n>>s;


for (ll i=1;i<=n;i++){
    string s;
    cin>>s;
    for (ll j=1;j<=n;j++){
        arr[i][j]=s[j-1];

        if(arr[i][j]=="M")mecho=mpa(i,j);
        else if (arr[i][j]=="D")home = mpa(i,j);
    }
}

queue <pair<ll,ll>> q;
q.push(mecho);
vist[mecho.fi][mecho.se]=true;

while(!q.empty()){
    auto p = q.front();
    ll x = p.fi;
    ll y = p.se;

    q.pop();

    for (ll i=0;i<4;i++){
        ll nx = x+dx[i];
        ll ny = y+dy[i];

        if(valid(nx,ny)&&arr[nx][ny]!="H"){
            mechoDist[nx][ny]=mechoDist[x][y]+1;
            vist[nx][ny]=true;
            q.push(mpa(nx,ny));
        }
    }

}


for (ll i=1;i<=n;i++)for(ll j=1;j<=n;j++){
mechoDist[i][j]=mechoDist[i][j]/s;
vist[i][j]=false;
}



for (ll i=1;i<=n;i++)for (ll j=1;j<=n;j++){
    if(arr[i][j]=="H"){
            q.push(mpa(i,j));
            vist[i][j]=true;
    }
}



while(!q.empty()){
    auto p = q.front();
    ll x = p.fi;
    ll y = p.se;
    q.pop();

    for (ll i=0;i<4;i++){
        ll nx = x+dx[i];
        ll ny = y+dy[i];

        if(valid(nx,ny)&&arr[nx][ny]!="D"&&arr[nx][ny]!="H"){
            BeesDist[nx][ny]=BeesDist[x][y]+1;
            vist[nx][ny]=true;
            q.push(mpa(nx,ny));
        }
    }

}


/*cout<<endl<<endl;
for(ll i=1;i<=n;i++){for (ll j=1;j<=n;j++){
        if(arr[i][j]=="G")
     cout<<mechoDist[i][j];
     else cout<<arr[i][j];
}
cout<<endl;
}

cout<<endl<<endl;
for(ll i=1;i<=n;i++){for (ll j=1;j<=n;j++){
    cout<<BeesDist[i][j];
}
cout<<endl;
}*/




ll l=0;
ll r = 1e9;
ll ans =-1;
while (l<=r){
    ll mid = (l+r)/2;
    for (ll i=1;i<=n;i++)for(ll j=1;j<=n;j++){
 vist[i][j]=false;
}
check=false;
bfs(mid);

if(check){
    l=mid+1;
    ans = mid;

} else {
r=mid-1;
}



}

cout<<ans;
return 0;


}





unsigned long long power(unsigned long long x,
                                ll y, ll p)
{
    unsigned long long res = 1; // Initialize result

    x = x % p; // Update x if it is more than or
    // equal to p

    while (y > 0)
    {

        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}

unsigned long long modInverse(unsigned long long n,
                                            ll p)
{
    return power(n, p - 2, p);
}

Subtask #1
24.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 20436 KB Output is correct
2 Incorrect 12 ms 20436 KB Output isn't correct
3 Correct 10 ms 20472 KB Output is correct
4 Correct 11 ms 20436 KB Output is correct
5 Correct 10 ms 20436 KB Output is correct
6 Incorrect 10 ms 20464 KB Output isn't correct
7 Incorrect 349 ms 31276 KB Output isn't correct
8 Correct 11 ms 20564 KB Output is correct
9 Correct 11 ms 20564 KB Output is correct
10 Correct 10 ms 20524 KB Output is correct
11 Correct 10 ms 20692 KB Output is correct
12 Incorrect 12 ms 20948 KB Output isn't correct
13 Correct 13 ms 20948 KB Output is correct
14 Correct 11 ms 20948 KB Output is correct
15 Incorrect 11 ms 20564 KB Output isn't correct
16 Incorrect 11 ms 20564 KB Output isn't correct
17 Incorrect 10 ms 20692 KB Output isn't correct
18 Incorrect 10 ms 20652 KB Output isn't correct
19 Incorrect 11 ms 20692 KB Output isn't correct
20 Incorrect 11 ms 20692 KB Output isn't correct
21 Incorrect 11 ms 20820 KB Output isn't correct
22 Incorrect 13 ms 20820 KB Output isn't correct
23 Incorrect 12 ms 20944 KB Output isn't correct
24 Incorrect 11 ms 20948 KB Output isn't correct
25 Incorrect 11 ms 20948 KB Output isn't correct
26 Incorrect 13 ms 20948 KB Output isn't correct
27 Incorrect 12 ms 21076 KB Output isn't correct
28 Incorrect 11 ms 21036 KB Output isn't correct
29 Incorrect 11 ms 21080 KB Output isn't correct
30 Incorrect 11 ms 21056 KB Output isn't correct
31 Incorrect 11 ms 21204 KB Output isn't correct
32 Incorrect 12 ms 21180 KB Output isn't correct
33 Incorrect 31 ms 24628 KB Output isn't correct
34 Incorrect 30 ms 24892 KB Output isn't correct
35 Incorrect 81 ms 25128 KB Output isn't correct
36 Incorrect 32 ms 25320 KB Output isn't correct
37 Incorrect 31 ms 25604 KB Output isn't correct
38 Incorrect 106 ms 25804 KB Output isn't correct
39 Incorrect 36 ms 25972 KB Output isn't correct
40 Incorrect 38 ms 26380 KB Output isn't correct
41 Incorrect 126 ms 26472 KB Output isn't correct
42 Incorrect 38 ms 26576 KB Output isn't correct
43 Incorrect 38 ms 26988 KB Output isn't correct
44 Incorrect 179 ms 27152 KB Output isn't correct
45 Incorrect 48 ms 27068 KB Output isn't correct
46 Incorrect 49 ms 27740 KB Output isn't correct
47 Incorrect 196 ms 27848 KB Output isn't correct
48 Incorrect 51 ms 27736 KB Output isn't correct
49 Incorrect 58 ms 28300 KB Output isn't correct
50 Incorrect 247 ms 28492 KB Output isn't correct
51 Incorrect 58 ms 28404 KB Output isn't correct
52 Incorrect 65 ms 28876 KB Output isn't correct
53 Incorrect 275 ms 29172 KB Output isn't correct
54 Incorrect 82 ms 28932 KB Output isn't correct
55 Incorrect 79 ms 29564 KB Output isn't correct
56 Incorrect 314 ms 29884 KB Output isn't correct
57 Incorrect 69 ms 29532 KB Output isn't correct
58 Incorrect 80 ms 30208 KB Output isn't correct
59 Incorrect 370 ms 30504 KB Output isn't correct
60 Incorrect 81 ms 30196 KB Output isn't correct
61 Incorrect 88 ms 30624 KB Output isn't correct
62 Incorrect 434 ms 31048 KB Output isn't correct
63 Correct 325 ms 31120 KB Output is correct
64 Correct 509 ms 31140 KB Output is correct
65 Correct 477 ms 31160 KB Output is correct
66 Correct 368 ms 31164 KB Output is correct
67 Correct 327 ms 31128 KB Output is correct
68 Correct 182 ms 31180 KB Output is correct
69 Correct 183 ms 31220 KB Output is correct
70 Correct 151 ms 31180 KB Output is correct
71 Correct 151 ms 31096 KB Output is correct
72 Correct 138 ms 31100 KB Output is correct
73 Correct 189 ms 31744 KB Output is correct
74 Incorrect 212 ms 31616 KB Output isn't correct
75 Incorrect 252 ms 31608 KB Output isn't correct
76 Incorrect 223 ms 31780 KB Output isn't correct
77 Incorrect 240 ms 31696 KB Output isn't correct
78 Correct 232 ms 31644 KB Output is correct
79 Incorrect 226 ms 31740 KB Output isn't correct
80 Incorrect 207 ms 31632 KB Output isn't correct
81 Incorrect 255 ms 31632 KB Output isn't correct
82 Incorrect 227 ms 31572 KB Output isn't correct
83 Incorrect 295 ms 31556 KB Output isn't correct
84 Incorrect 274 ms 31648 KB Output isn't correct
85 Incorrect 269 ms 31476 KB Output isn't correct
86 Incorrect 300 ms 31436 KB Output isn't correct
87 Incorrect 303 ms 31556 KB Output isn't correct
88 Incorrect 314 ms 31464 KB Output isn't correct
89 Incorrect 325 ms 31488 KB Output isn't correct
90 Incorrect 321 ms 31436 KB Output isn't correct
91 Incorrect 322 ms 31568 KB Output isn't correct
92 Incorrect 320 ms 31360 KB Output isn't correct