Submission #906636

#	Time	Username	Problem	Language	Result	Execution time	Memory
906636		tosivanmak	Mecho (IOI09_mecho)	C++17	70 / 100	706 ms	65536 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define ll int
 
ll dx[4]={0,0,1,-1};
ll dy[4]={1,-1,0,0};
vector<pair<short,short> >pos;
struct Graph{
 bool vis[802][802];
 ll dist[802][802];
    vector<pair<short,short> >adj[802][802];
 queue<pair<short,short> >q;
    void init(ll n){
        for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    dist[i][j]=1e9;
                }
            }
    }
    void add_edge(ll r, ll c, ll r2, ll c2){
        adj[r][c].push_back({r2,c2});
    }
 void bfs(){
   for(auto& u: pos){
      vis[u.first][u.second]=1;
       dist[u.first][u.second]=0;
       q.push({u.first,u.second});
   }
   while(!q.empty()){
       pair<ll,ll>cur=q.front();
       q.pop();
       for(auto& u: adj[cur.first][cur.second]){
           if(!vis[u.first][u.second]){
               vis[u.first][u.second]=1;
               dist[u.first][u.second]=dist[cur.first][cur.second]+1;
               q.push(u);
           }
       }
   }
}
}gp2;
struct Graph2{
 bool vis[802][802];
    vector<pair<short,short> >adj[802][802];
 queue<pair<short,short> >q;
    ll bees[802][802];
    ll dist[802][802];
    void add_edge(ll r, ll c, ll r2, ll c2){
        adj[r][c].push_back({r2,c2});
    }
 void bfs(ll r, ll c, ll para, ll divi){
     vis[r][c]=1;
     dist[r][c]=0;
     q.push({r,c});
   while(!q.empty()){
       pair<ll,ll>cur=q.front();
       q.pop();
       for(auto& u: adj[cur.first][cur.second]){
           // cout<<bees[u.first][u.second]<<'\n';
           // cout<<dist[cur.first][cur.second]+1<<" "<<(ll)(divi+1)*(ll)bees[u.first][u.second]-(ll)1<<'\n';
           long long lol=divi;
           lol*=((long long)bees[u.first][u.second]-(long long)para);
           lol--;
           long long lol2=dist[cur.first][cur.second];
           lol2++;
           // cout<<lol<<'\n';
           // if(lol<0){
           //     cout<<divi+1<<" "<<bees[u.first][u.second]<<'\n';
           // }
           if(!vis[u.first][u.second]&&(lol2<=lol)){
               // cout<<u.first<<" "<<u.second<<'\n';
               vis[u.first][u.second]=1;
               dist[u.first][u.second]=dist[cur.first][cur.second]+1;
               q.push(u);
           }
       }
   }
 }
    void clear(ll n){
        for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    // cout<<bees[i][j]<<" ";
                    vis[i][j]=0;
                    dist[i][j]=1e9;
                }
            // cout<<'\n';
            }
        }
    bool ck(ll r, ll c, ll n, ll par, ll finr, ll finc, ll divi){
        clear(n);
        bfs(r,c,par,divi);
        if(vis[finr][finc]){
            return 1;
        }
        return 0;
    }
}gp3;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n,s;
    cin>>n>>s;
    char arr[n+2][n+2];
gp2.init(n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>arr[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=0;k<4;k++){
                if(arr[i][j]=='M'||arr[i][j]=='G'||arr[i][j]=='D'){
                 if(arr[i+dx[k]][j+dy[k]]=='M'||arr[i+dx[k]][j+dy[k]]=='G'||arr[i+dx[k]][j+dy[k]]=='D'){
                     gp3.add_edge(i,j,i+dx[k],j+dy[k]);
                 }
                }
                if(arr[i][j]=='M'||arr[i][j]=='G'||arr[i][j]=='H'){
                 if(arr[i+dx[k]][j+dy[k]]=='M'||arr[i+dx[k]][j+dy[k]]=='G'||arr[i+dx[k]][j+dy[k]]=='H'){
                    gp2.add_edge(i,j,i+dx[k],j+dy[k]);
                 }
                }
            }
            if(arr[i][j]=='H'){
                pos.push_back({i,j});
            }
        }
    }
    gp2.bfs();
    pos.clear();
    ll startr,startc,endr,endc;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(arr[i][j]=='M'){
                startr=i,startc=j;
            }
            if(arr[i][j]=='D'){
                endr=i,endc=j;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            gp3.bees[i][j]=gp2.dist[i][j];
            }
        }
    pos.clear();
    
    ll l=0,r=gp2.dist[startr][startc]-1;
    while(l<=r){
        if(l==r){
            break;
        }
        else if(l==r-1){
            if(gp3.ck(startr,startc,n,r,endr,endc,s)){
                l=r;
            }
            else{
                r=l;
            }
            break;
        }
        else{
            ll mid=(l+r)>>1;
            if(gp3.ck(startr,startc,n,mid,endr,endc,s)){
                l=mid;
            }
            else{
                r=mid;
            }
        }
    }
    // cout<<'\n';
    // cout<<l<<'\n';
    if(!gp3.ck(startr,startc,n,l,endr,endc,s)){
        cout<<"-1\n";
    }
    else{
        cout<<l<<'\n';
    }
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:176:15: warning: 'startr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  176 |     if(!gp3.ck(startr,startc,n,l,endr,endc,s)){
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:176:15: warning: 'endr' may be used uninitialized in this function [-Wmaybe-uninitialized]
mecho.cpp:176:15: warning: 'endc' may be used uninitialized in this function [-Wmaybe-uninitialized]
mecho.cpp:176:15: warning: 'startc' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 70 / 100