Submission #1329292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1329292		moondarkside	Mecho (IOI09_mecho)	C++20	0 / 100	427 ms	131072 KiB

mecho

#include<bits/stdc++.h>
using namespace std;

#define int short

std::vector<vector<int>>map;
std::vector<vector<int>>Time;

bool CheckPossible(int ST,int s,pair<int,int> Start,vector<vector<int>> Time,int n){
    std::queue<pair<pair<int,int>,int>>Expand;
    if(Time[Start.first][Start.second]<=ST){
        return false;
    }
    Expand.push({{Start.first,Start.second},0});
    while(!Expand.empty()){
        
        
        int x=Expand.front().first.first;
        int y=Expand.front().first.second;
        int t=Expand.front().second;
        

        
        if(x>0 && Time[x-1][y]>ST+((t+1)/s)){
            Expand.push({{x-1,y},t+1});
        }
        if(x<n-1 && Time[x+1][y]>ST+((t+1)/s)){
            Expand.push({{x+1,y},t+1});
        }
        
        if(y>0 && Time[x][y-1]>ST+((t+1)/s)){
            Expand.push({{x,y-1},t+1});
        }
        if(y<n-1 && Time[x][y+1]>ST+((t+1)/s)){
            Expand.push({{x,y+1},t+1});
        }
        
        
        
        if(Time[x][y]==100000){
            
            return true;
        }
        Time[x][y]=-1;
        

        Expand.pop();
        
        
    }
    return false;
    
    



}

signed main(){
    
    int n,s;
    cin>>n>>s;
    pair<int,int> start;
    Time=vector<vector<int>>(n,vector<int>(n,-1));
    std::queue<pair<pair<int,int>,int>>Expand;
    
    for(int x=0;x<n;x++){
        
        for(int y=0;y<n;y++){
        
            char c;
            cin>>c;
            if(c=='T'){
                Time[x][y]=0;
            }
            if(c=='M'){
                start={x,y};
            }
            if(c=='D'){
                Time[x][y]=100000;
            }
            if(c=='H'){
                Time[x][y]=0;
                Expand.push({{x,y},0});
            }
        
        }
    }
    
    while(!Expand.empty()){
        
        int x=Expand.front().first.first;
        int y=Expand.front().first.second;
        int t=Expand.front().second;
        
        if(x>0 && Time[x-1][y]==-1){
            Time[x-1][y]=t+1;
            Expand.push({{x-1,y},t+1});
        }
        if(x<n-1 && Time[x+1][y]==-1){
            Time[x+1][y]=t+1;
            Expand.push({{x+1,y},t+1});
        }
        
        if(y>0 && Time[x][y-1]==-1){
            Time[x][y-1]=t+1;
            Expand.push({{x,y-1},t+1});
        }
        if(y<n-1 && Time[x][y+1]==-1){
            Time[x][y+1]=t+1;
            Expand.push({{x,y+1},t+1});
        }
        
        Expand.pop();
    }
    
    
    
   if(!CheckPossible(0,s,start,Time,n)){
        cout<<-1<<endl;
        return 0;
    }
    int min=0;
    int max=1000;
    
    while(min<max){
        int m=(min+max-1)/2+1;
        
        if(CheckPossible(m,s,start,Time,n)){
            min=m;
        }else{
            max=m-1;
        }
        
    }
    cout<<min<<endl;
    return 0;
    
    
    
}

Compilation message (stderr)

mecho.cpp: In function 'bool CheckPossible(short int, short int, std::pair<short int, short int>, std::vector<std::vector<short int> >, short int)':
mecho.cpp:25:35: warning: narrowing conversion of '(((int)t) + 1)' from 'int' to 'short int' [-Wnarrowing]
   25 |             Expand.push({{x-1,y},t+1});
      |                                  ~^~
mecho.cpp:28:35: warning: narrowing conversion of '(((int)t) + 1)' from 'int' to 'short int' [-Wnarrowing]
   28 |             Expand.push({{x+1,y},t+1});
      |                                  ~^~
mecho.cpp:32:35: warning: narrowing conversion of '(((int)t) + 1)' from 'int' to 'short int' [-Wnarrowing]
   32 |             Expand.push({{x,y-1},t+1});
      |                                  ~^~
mecho.cpp:35:35: warning: narrowing conversion of '(((int)t) + 1)' from 'int' to 'short int' [-Wnarrowing]
   35 |             Expand.push({{x,y+1},t+1});
      |                                  ~^~
mecho.cpp: In function 'int main()':
mecho.cpp:80:28: warning: overflow in conversion from 'int' to '__gnu_cxx::__alloc_traits<std::allocator<short int>, short int>::value_type' {aka 'short int'} changes value from '100000' to '-31072' [-Woverflow]
   80 |                 Time[x][y]=100000;
      |                            ^~~~~~
mecho.cpp:98:35: warning: narrowing conversion of '(((int)t) + 1)' from 'int' to 'short int' [-Wnarrowing]
   98 |             Expand.push({{x-1,y},t+1});
      |                                  ~^~
mecho.cpp:102:35: warning: narrowing conversion of '(((int)t) + 1)' from 'int' to 'short int' [-Wnarrowing]
  102 |             Expand.push({{x+1,y},t+1});
      |                                  ~^~
mecho.cpp:107:35: warning: narrowing conversion of '(((int)t) + 1)' from 'int' to 'short int' [-Wnarrowing]
  107 |             Expand.push({{x,y-1},t+1});
      |                                  ~^~
mecho.cpp:111:35: warning: narrowing conversion of '(((int)t) + 1)' from 'int' to 'short int' [-Wnarrowing]
  111 |             Expand.push({{x,y+1},t+1});
      |                                  ~^~

• Subtask 1: 0 / 100