답안 #1083309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1083309	2024-09-02T22:23:23 Z	hohemhein	Mecho (IOI09_mecho)	C++17	22 / 100	45 ms	12448 KB

mecho

#include <bits/stdc++.h>
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define f first
#define s second
#define pb push_back
#define pu push
#define ll long long
#define int long long
#define endl "\n"
#define all(x) (x).begin() , (x).end()
using namespace std;
const int nmax = 8e2+4;
const int oo = 1e12+3;
const ll mod = 1e9+7;

char m[nmax][nmax];
int bee[nmax][nmax];
int bear[nmax][nmax];

int mov[] = { 1,-1 };


void llenar(){

   for( int i = 0; i < nmax; i++ ){
    fill( bear[i], bear[i]+nmax, oo );
    fill( bee[i], bee[i]+nmax, oo );
   }

}

void bfsBee( vector<ii>&aux, int n ){
  queue<ii>c;
  for( auto [i,j] : aux ){
        c.pu({i,j});
        bee[i][j] = 0;
  }

  while( !c.empty() ){
     auto [x,y] = c.front();
     c.pop();

     for( int i = 0; i < 2; i++ )
        if( x+mov[i] > 0 && x+mov[i] <= n && m[ x+mov[i] ][y] == 'G' && bee[ x+mov[i] ][y] == oo ){
           c.pu( {x+mov[i],y} );
           bee[ x+mov[i] ][y] = bee[x][y]+1;
     }

     for( int i = 0; i < 2; i++ )
        if( y+mov[i] > 0 && y+mov[i] <= n && m[x][y+mov[i]] == 'G' && bee[x][y+mov[i]] == oo ){
           c.pu( {x,y+mov[i]} );
           bee[x][y+mov[i]] = bee[x][y]+1;
     }


  }

}


void bfsBear( ii X, int n, int k ){
  queue<iii>c;
  c.pu({{X.f,X.s},0});
  bear[X.f][X.s] = bee[X.f][X.s] -1;

  while( !c.empty() ){
     auto [x,y] = c.front().f; int pe = c.front().s;
     c.pop();
     for( int i = 0; i < 2; i++ )
        if( x+mov[i] > 0 && x+mov[i] <= n && m[ x+mov[i] ][y] != 'T' && bear[ x+mov[i] ][y] == oo && bee[ x+mov[i] ][y] > pe/k ){
           c.pu( { {x+mov[i],y}, pe+1 } );
           bear[ x+mov[i] ][y] = min( bear[x][y] , bee[ x+mov[i] ][y] - pe/k - 1 );
     }

     for( int i = 0; i < 2; i++ )
        if( y+mov[i] > 0 && y+mov[i] <= n && m[x][y+mov[i]] != 'T'&& bear[x][y+mov[i]] == oo && bee[x][y+mov[i]] > pe/k ){
           c.pu( {{x,y+mov[i]},pe+1} );
           bear[x][y+mov[i]] =  min( bear[x][y] , bee[x][y+mov[i]] - pe/k - 1 );
     }


  }

}



int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie();
    //cout << fixed << setprecision(4);

    /*ifstream cin ("atlarge.in");
    ofstream cout ("atlarge.out");*/


    llenar();

    int n, k; cin >> n >> k;
    ii init, meta;

    vector<ii>aux;

    for( int i = 1; i <= n; i++ )
        for( int j = 1; j <= n; j++ ){
            cin >> m[i][j];
            if( m[i][j] == 'H' )aux.pb({i,j});
            else if( m[i][j] == 'M' )init = {i,j};
            else if( m[i][j] == 'D' )meta = {i,j};
        }

     bfsBee( aux, n );

     bfsBear( init, n, k);

     if( bear[meta.f][meta.s] != oo )cout << bear[meta.f][meta.s];
     else cout <<"-1\n";

    return 0;
}

Subtask #1

22.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	6 ms	10588 KB	Output isn't correct
2	Incorrect	5 ms	10588 KB	Output isn't correct
3	Incorrect	4 ms	10372 KB	Output isn't correct
4	Incorrect	5 ms	10360 KB	Output isn't correct
5	Correct	4 ms	10588 KB	Output is correct
6	Correct	4 ms	10584 KB	Output is correct
7	Incorrect	29 ms	11864 KB	Output isn't correct
8	Incorrect	4 ms	10588 KB	Output isn't correct
9	Correct	4 ms	10588 KB	Output is correct
10	Correct	6 ms	10500 KB	Output is correct
11	Correct	5 ms	10588 KB	Output is correct
12	Incorrect	4 ms	10520 KB	Output isn't correct
13	Correct	4 ms	10588 KB	Output is correct
14	Correct	5 ms	10580 KB	Output is correct
15	Incorrect	4 ms	10584 KB	Output isn't correct
16	Correct	4 ms	10588 KB	Output is correct
17	Incorrect	4 ms	10440 KB	Output isn't correct
18	Correct	4 ms	10588 KB	Output is correct
19	Incorrect	4 ms	10588 KB	Output isn't correct
20	Correct	4 ms	10588 KB	Output is correct
21	Incorrect	4 ms	10588 KB	Output isn't correct
22	Correct	4 ms	10496 KB	Output is correct
23	Incorrect	5 ms	10584 KB	Output isn't correct
24	Correct	4 ms	10588 KB	Output is correct
25	Incorrect	4 ms	10588 KB	Output isn't correct
26	Correct	4 ms	10588 KB	Output is correct
27	Incorrect	4 ms	10588 KB	Output isn't correct
28	Correct	4 ms	10588 KB	Output is correct
29	Incorrect	4 ms	10588 KB	Output isn't correct
30	Correct	4 ms	10588 KB	Output is correct
31	Incorrect	5 ms	10564 KB	Output isn't correct
32	Correct	4 ms	10588 KB	Output is correct
33	Incorrect	7 ms	10904 KB	Output isn't correct
34	Correct	7 ms	10844 KB	Output is correct
35	Incorrect	8 ms	10968 KB	Output isn't correct
36	Incorrect	8 ms	10844 KB	Output isn't correct
37	Correct	8 ms	10876 KB	Output is correct
38	Incorrect	10 ms	10844 KB	Output isn't correct
39	Incorrect	8 ms	11096 KB	Output isn't correct
40	Correct	8 ms	10984 KB	Output is correct
41	Incorrect	11 ms	10908 KB	Output isn't correct
42	Incorrect	9 ms	11100 KB	Output isn't correct
43	Correct	9 ms	11096 KB	Output is correct
44	Incorrect	12 ms	11068 KB	Output isn't correct
45	Incorrect	11 ms	11136 KB	Output isn't correct
46	Correct	10 ms	11232 KB	Output is correct
47	Incorrect	14 ms	11100 KB	Output isn't correct
48	Incorrect	11 ms	11356 KB	Output isn't correct
49	Correct	20 ms	11356 KB	Output is correct
50	Incorrect	28 ms	11428 KB	Output isn't correct
51	Incorrect	12 ms	11356 KB	Output isn't correct
52	Correct	12 ms	11336 KB	Output is correct
53	Incorrect	18 ms	11356 KB	Output isn't correct
54	Incorrect	14 ms	11612 KB	Output isn't correct
55	Correct	14 ms	11500 KB	Output is correct
56	Incorrect	21 ms	11612 KB	Output isn't correct
57	Incorrect	16 ms	11608 KB	Output isn't correct
58	Correct	17 ms	11612 KB	Output is correct
59	Incorrect	28 ms	11624 KB	Output isn't correct
60	Incorrect	17 ms	11836 KB	Output isn't correct
61	Correct	19 ms	11836 KB	Output is correct
62	Incorrect	32 ms	11632 KB	Output isn't correct
63	Correct	33 ms	11864 KB	Output is correct
64	Correct	45 ms	11612 KB	Output is correct
65	Correct	34 ms	11752 KB	Output is correct
66	Incorrect	34 ms	11612 KB	Output isn't correct
67	Correct	29 ms	11612 KB	Output is correct
68	Correct	35 ms	11864 KB	Output is correct
69	Correct	29 ms	11660 KB	Output is correct
70	Correct	27 ms	11868 KB	Output is correct
71	Correct	23 ms	11868 KB	Output is correct
72	Incorrect	32 ms	11868 KB	Output isn't correct
73	Incorrect	28 ms	12272 KB	Output isn't correct
74	Correct	32 ms	12380 KB	Output is correct
75	Correct	29 ms	12428 KB	Output is correct
76	Correct	31 ms	12236 KB	Output is correct
77	Correct	24 ms	12448 KB	Output is correct
78	Correct	30 ms	12248 KB	Output is correct
79	Incorrect	34 ms	12384 KB	Output isn't correct
80	Incorrect	26 ms	12388 KB	Output isn't correct
81	Incorrect	27 ms	12380 KB	Output isn't correct
82	Incorrect	25 ms	12380 KB	Output isn't correct
83	Correct	29 ms	12124 KB	Output is correct
84	Incorrect	34 ms	12132 KB	Output isn't correct
85	Incorrect	26 ms	12124 KB	Output isn't correct
86	Incorrect	26 ms	12124 KB	Output isn't correct
87	Incorrect	29 ms	12276 KB	Output isn't correct
88	Correct	30 ms	12124 KB	Output is correct
89	Incorrect	36 ms	12124 KB	Output isn't correct
90	Incorrect	26 ms	12120 KB	Output isn't correct
91	Incorrect	36 ms	12168 KB	Output isn't correct
92	Incorrect	29 ms	12124 KB	Output isn't correct