Submission #135813

#	Time	Username	Problem	Language	Result	Execution time	Memory
135813		Dilshod_Imomov	Mecho (IOI09_mecho)	C++17	28 / 100	1091 ms	15108 KiB

mecho

# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
# define pb push_back
# define pf push_front
# define For(i, a, b) for( int i = a; i < b; i++ )
# define in insert
# define all(a) a.begin(),a.end()
# define pi pair < int, int >
# define DEBUG
# define readfile(file) freopen ( (file + ".in").c_str(), "r", stdin)
# define writefile(file) freopen ( (file + ".out").c_str(), "w", stdout)
# define speed ios_base::sync_with_stdio(false);cin.tie(NULL)
# define LARGE (1e7)
# define SET(file) readfile(file);writefile(file);

using namespace std;


int n, s, cnt, ans = -1;
int visited[805][805], step[805][805], check[805];

vector < string > forest, forest1, forest2;
string m;

pi pos = {-1, -1};
pi add[] = { {1, 0}, {-1, 0}, {0, -1}, {0, 1} };

int valid ( pi pos ){
    int i = pos.fi, j = pos.se;

    if ( i >= 0 && i < n && j >= 0 && j < n && forest[i][j] != 'T' )
        return 1;
    return 0;
}

void spread(){
    vector < pi > pos;

    For ( i, 0, n )
        For ( j, 0, n )
            if ( forest[i][j] == 'H' )
                pos.pb( {i, j} );
    For ( i, 0, pos.size() )
        For ( j, 0, 4 ){
            pi to = { pos[i].fi + add[j].fi, pos[i].se + add[j].se };

            if ( valid(to) && forest[to.fi][to.se] != 'D' ){
                forest[to.fi][to.se] = 'H';
                cnt++;
            }
        }
}

int main(){
    /// Author: _Dilshod_
    speed;
    cin >> n >> s;

    For ( i, 0, n ){
        cin >> m;
        forest.pb(m);
        forest1.pb(m);

        if ( pos.fi == -1 )
            For ( j, 0, m.size() )

                if ( m[j] == 'M' )
                    pos = {i, j};
    }
    for ( int x = 0; x > -1; x++ ){

        For ( i, 0, 805 )
            For ( j, 0, 805 ){
                visited[i][j] = 0;
                step[i][j] = 0;
                check[j] = 0;
            }
        queue < pi > BFS;
        BFS.push(pos);
        visited[pos.fi][pos.se] = 1;
        forest = forest1;
        cnt = 0;
        int ans1 = -1;

        For ( i, 0, x ){
            spread();
            if ( !cnt )
                break;
            cnt = 0;
        }
        while( !BFS.empty() ){
            pi loc = BFS.front();
            BFS.pop();
            visited[loc.fi][loc.se] = 1;
            int st = step[loc.fi][loc.se];

            if ( forest[loc.fi][loc.se] == 'D' ){
                ans1 = x;
                break;
            }
            if ( forest[loc.fi][loc.se] == 'H' )
                continue;
            if ( !(st % s) && st != 0 && !check[st] ){
                forest2 = forest;
                spread();

                if ( forest[loc.fi][loc.se] == 'H' ){
                    forest = forest2;
                    continue;
                }
                check[st] = 1;
            }
            For ( i, 0, 4 ){
                pi to = { loc.fi + add[i].fi, loc.se + add[i].se };

                if ( valid( to ) && !visited[to.fi][to.se] ){
                    visited[to.fi][to.se] = 1;
                    step[to.fi][to.se] = st + 1;
                    BFS.push(to);
                }
            }
        }
        if ( ans1 == -1 )
            break;
        ans = max( ans, ans1 );
    }
    cout << ans;
}

Compilation message (stderr)

mecho.cpp: In function 'void spread()':
mecho.cpp:7:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 # define For(i, a, b) for( int i = a; i < b; i++ )
mecho.cpp:45:11:
     For ( i, 0, pos.size() )
           ~~~~~~~~~~~~~~~~               
mecho.cpp:45:5: note: in expansion of macro 'For'
     For ( i, 0, pos.size() )
     ^~~
mecho.cpp: In function 'int main()':
mecho.cpp:7:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 # define For(i, a, b) for( int i = a; i < b; i++ )
mecho.cpp:67:19:
             For ( j, 0, m.size() )
                   ~~~~~~~~~~~~~~         
mecho.cpp:67:13: note: in expansion of macro 'For'
             For ( j, 0, m.size() )
             ^~~

• Subtask 1: 28 / 100