Submission #135481

#	Time	Username	Problem	Language	Result	Execution time	Memory
135481		Dilshod_Imomov	Mecho (IOI09_mecho)	C++17	9 / 100	1092 ms	17596 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)

using namespace std;
void Set_File( string file ){readfile(file);writefile(file);}

int n, s;
string m;
vector < string > forest;
vector < string > forest1;
int step[1000][1000];
int visited[1000][1000];
int x, ans = -1;
pi pos = { -1, -1 };
vector < pi > add = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

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

void spread_bees(){
    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 neighbour = { pos[i].fi + add[j].fi, pos[i].se + add[j].se };
            if ( valid( neighbour.fi, neighbour.se ) && forest[neighbour.fi][neighbour.se] == 'G' && forest[neighbour.fi][neighbour.se] != 'D' ){
                forest[neighbour.fi][neighbour.se] = 'H';
            }
        }
    }
}

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};
                }
            }
        }
    }
    while ( 1 ){
        int ans1 = -1;
        queue < pi > BFS;
        BFS.push(pos);
        forest = forest1;

        For ( i, 0, 1000 ){
            For ( j, 0, 1000 ){
                step[i][j] = 0;
                visited[i][j] = 0;
            }
        }
        For ( i, 0, x ){
            spread_bees();
        }
        int y = x;
        int z = 0;
        pi loc = pos;
        visited[loc.fi][loc.se] = 1;

        while ( !BFS.empty() ){
            loc = BFS.front();

            if ( step[loc.fi][loc.se] == 0 ){
                spread_bees();
                y++;
            }
            if ( step[loc.fi][loc.se] == 1 && z ){
                z = 0;
                spread_bees();
                y++;
            }
            if ( forest[loc.fi][loc.se] == 'D' ){
                ans1 = max( ans1, x );
                break;
            }
            BFS.pop();

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

                if ( valid( to.fi, to.se ) && !visited[to.fi][to.se] ) {
                    visited[to.fi][to.se] = 1;

                    if ( step[loc.fi][loc.se] == 2 ) {
                        z++;
                    }
                    step[to.fi][to.se] = step[loc.fi][loc.se] + 1;
                    BFS.push(to);
                }
            }
            if ( BFS.empty() && forest[loc.fi][loc.se] != 'D' ) {
                ans1 = -1;
                break;
            }
        }
        x++;
        ans = max( ans1, ans );

        if ( ans1 == -1 ){
            break;
        }
    }
    cout << ans;
}

Compilation message (stderr)

mecho.cpp: In function 'void spread_bees()':
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:47:11:
     For ( i, 0, pos.size() ){
           ~~~~~~~~~~~~~~~~               
mecho.cpp:47: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:68:19:
             For ( j, 0, m.size() ){
                   ~~~~~~~~~~~~~~         
mecho.cpp:68:13: note: in expansion of macro 'For'
             For ( j, 0, m.size() ){
             ^~~
mecho.cpp: In function 'void Set_File(std::__cxx11::string)':
mecho.cpp:12:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 # define readfile(file) freopen ( (file + ".in").c_str(), "r", stdin)
                         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:18:30: note: in expansion of macro 'readfile'
 void Set_File( string file ){readfile(file);writefile(file);}
                              ^~~~~~~~
mecho.cpp:13:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 # define writefile(file) freopen ( (file + ".out").c_str(), "w", stdout)
                          ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:18:45: note: in expansion of macro 'writefile'
 void Set_File( string file ){readfile(file);writefile(file);}
                                             ^~~~~~~~~

• Subtask 1: 9 / 100