제출 #1121076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121076		sktodow	Mecho (IOI09_mecho)	C++17	28 / 100	178 ms	12884 KiB

mecho

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
#define int long long int
#define pb push_back
#define mid (l+(r-l)/2)
#define f first
#define s second
static const int N=805;
static const int MOD=(1LL<<61)-1;
static const int inf=N*N+5;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
 
void io(string name = ""){ 
    freopen((name+".in").c_str(), "r", stdin);
    freopen((name+".out").c_str(), "w", stdout);
}
 
int n,s,mx,my,hx,hy;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

vector<vector<char>>v(N,vector<char>(N));
vector<vector<int>>bee(N,vector<int>(N,inf));
vector<vector<int>>mec(N,vector<int>(N,inf));
vector<vector<bool>>vis(N,vector<bool>(N,0));

bool inside(int i,int j){ return ((i>0&&i<=n) && (j>0&&j<=n) && (v[i][j]=='M' || v[i][j]=='G'));}

void calcbee(){
    queue<array<int,3>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(v[i][j]=='H'){q.push({i,j,0});bee[i][j]=0;}
        }
    }
    while(q.size()){
        array<int,3>c=q.front();
        q.pop();
        // if(bee[c[0]][c[1]]!=inf){continue;}
        for(int i=0;i<4;i++){
            int cx=c[0]+dx[i],cy=c[1]+dy[i];
            if(inside(cx,cy)&& bee[cx][cy]>c[2]+1){
                bee[cx][cy]=c[2]+1;
                q.push({cx,cy,c[2]+1});
            }
        }
    }
}

void mecho(int k){
    mec[mx][my]=k;
    queue<array<int,3>>q;
    q.push({mx,my,k});
    while(q.size()){
        array<int,3>c=q.front();
        q.pop();
        if(vis[c[0]][c[1]]){continue;}
        // cout<<'a';
        vis[c[0]][c[1]]=1;
        for(int i=0;i<4;i++){
            int cx=c[0]+dx[i],cy=c[1]+dy[i];
            // cout<<c[2]/s<<" ";
            if(inside(cx,cy) && mec[cx][cy]>c[2]+1 && (int)(c[2])/s < bee[cx][cy]){
                mec[cx][cy]=c[2]+1;
                q.push({cx,cy,c[2]+1});
            }
        }
    }
}
 
int32_t main(){
    //io("local");
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>v[i][j];
            if(v[i][j]=='M'){mx=i,my=j;}
            if(v[i][j]=='D'){hx=i,hy=j;}
        }
    }
    calcbee();
    // for(int i=1;i<=n;i++){
    //         for(int j=1;j<=n;j++){
    //             cout<<bee[i][j]<<" ";
    //         }cout<<endl;
    //     }
    int l=0,r=n*n;
    bool aaa=0;
    while(l<=r){
        for(int i=1;i<=n;i++){fill(mec[i].begin(),mec[i].end(),inf);}
        for(int i=1;i<=n;i++){fill(vis[i].begin(),vis[i].end(),0);}
        mecho(mid*s);
        bool chc=0;
        for(int i=0;i<n;i++){
            int cx=hx+dx[i],cy=hy+dy[i];
            if(inside(cx,cy) && vis[cx][cy]){chc=1;aaa=1;}
        }
        // cout<<mid<<" "<<chc<<endl;
        // for(int i=1;i<=n;i++){
        //     for(int j=1;j<=n;j++){
        //         cout<<mec[i][j]<<" ";
        //     }cout<<endl;
        // }

        if(chc){l=mid+1;}
        else{r=mid-1;}
    }
    if(aaa){cout<<l-1;}
    else{cout<<-1;}
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'void io(std::string)':
mecho.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen((name+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((name+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 28 / 100