Submission #1354279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354279		CowTheCow	Mecho (IOI09_mecho)	C++20	40 / 100	178 ms	11368 KiB

mecho

#include <bits/stdc++.h>

#define int long long
#define vi vector<int>
#define pb push_back
#define sz(a) a.size()
#define pii pair<int,int>
#define fi first
#define se second
#define all(a) a.begin(), a.end()

using namespace std;

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

const int MAXN=802;
const int INF=1e9;

int n,c;
int st,en;

char G [MAXN*MAXN];
int hive_dist [MAXN*MAXN];
int dist [MAXN*MAXN];

int ceil_div(int a, int b) {
    if(a%b==0) return (a/b);
    return (a/b)+1;
}

vi adj (int v) {
    vi ans;
    if(v-n>=0) {
        ans.pb(v-n);
    }
    if(v+n<n*n) {
        ans.pb(v+n);
    }
    if((v%n)>0) {
        ans.pb(v-1);
    }
    if((v%n)!=(n-1)) {
        ans.pb(v+1);
    }
    return ans;
}

bool ok (int delay) {
    queue<int> Q;
    Q.push(st);
    
    fill(dist, dist+n*n, INF);
    dist[st]=0;

    if(hive_dist[st]<=delay)
        return false;

    while(!Q.empty()) {
        int v=Q.front();
        Q.pop();

        for(int to:adj(v)) {
            if(dist[to]==INF&&G[to]!='T'&&G[to]!='H') {
                int ndist=dist[v]+1;

                if(ceil_div(ndist, c)+delay<=hive_dist[to]) {
                    dist[to]=ndist;
                    Q.push(to);
                    if(to==en)
                        return true;
                }
            }
        }
    }
    return false;
} 

void solve () {
    cin>>n>>c;
    
    queue<int> Q;
    fill(hive_dist, hive_dist+n*n, INF);
    for(int i=0;i<n;i++) {
        string s;
        cin>>s;
        for(int j=0;j<n;j++) {
            int p=i*n+j;

            G[p]=s[j];
            if(s[j]=='H') {
                Q.push(p);
                hive_dist[p]=0;
            }
            if(s[j]=='M') {
                st=p;
            }
            if(s[j]=='D') {
                en=p;
            }
        }
    }

    while(!Q.empty()) {
        int v=Q.front();
        Q.pop();

        for(int to:adj(v)) {
            if(hive_dist[to]==INF&&(G[to]=='M'||G[to]=='G')) {
                hive_dist[to]=hive_dist[v]+1;
                Q.push(to);
            }
        }
    }

    int ans=-1;
    int lo=0, hi=2*n;

    while(lo<=hi) {
        int mid=(lo+hi)/2;

        if(ok(mid)) {
            ans=mid;
            lo=mid+1;
        }else {
            hi=mid-1;
        }
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t=1;
    // cin>>t;

    while(t>0) {
        solve();
        t--;
    }
}

Compilation message (stderr)

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

• Subtask 1: 40 / 100