Submission #969073

#	Time	Username	Problem	Language	Result	Execution time	Memory
969073		anango	Mecho (IOI09_mecho)	C++17	39 / 100	799 ms	26028 KiB

mecho

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,s;
vector<vector<int>> dist;
vector<vector<int>> grid;
pair<int,int> start;
pair<int,int> finish;


int debug=0;
int INF=1000000007;
int gval(pair<int,int> cell) {
    return grid[cell.first][cell.second];
}

bool bounds(pair<int,int> cell) {
    return 0<=cell.first && cell.first<n && 0<=cell.second && cell.second<n;
}

vector<pair<int,int>> getnei(pair<int,int> st) {
    if (!(gval(st)==0)) {
        return {};
    }
    vector<pair<int,int>> V={{st.first-1,st.second},{st.first+1,st.second},{st.first,st.second+1},{st.first,st.second-1}};
    vector<pair<int,int>> ans;
    for (auto nei:V) {
        if (bounds(nei) && ((gval(nei)==0) || gval(nei)==2)) {
            ans.push_back(nei);
        }
    }
    return ans;
}

bool BSTA(int time) {
    //returns whether it can be done after waiting this time
    vector<vector<int>> distance(n,vector<int>(n,INF));
    vector<vector<int>> proc(n,vector<int>(n,0));
    deque<pair<int,int>> visited={start};
    distance[start.first][start.second] = 0;
    while (visited.size()) {
        pair<int,int> fi=visited[0];
        visited.pop_front();
        if (proc[fi.first][fi.second]) {
            continue;
        }
        proc[fi.first][fi.second] = 1;
        for (auto j:getnei(fi)) {
            int bdist=time+(distance[fi.first][fi.second]+1)/s; 
            //it's the total number of steps the honey has to walk to reach this cell
            if(debug) cout << fi.first << " " << fi.second << " " << j.first << " " << j.second << " "<<bdist << " " <<dist[fi.first][fi.second] << endl;
            if (bdist>=(dist[j.first][j.second])) {
                continue;
            }
            distance[j.first][j.second] = min(distance[j.first][j.second],distance[fi.first][fi.second]+1);
            visited.push_back(j);
        }
    }
    if(debug) cout << "BSTA TRYING METHOD CALCULATION TO FIND THE ANSWER" << " " << time << endl;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if(debug) cout << distance[i][j] <<" ";
        }
        if(debug) cout << endl;
    }
    return distance[finish.first][finish.second] < 3*n;
    
}


vector<pair<int,int>> adjlistbee(pair<int,int> st) {
    if (!(gval(st)==0 || gval(st)==3)) {
        return {};
    }
    vector<pair<int,int>> V={{st.first-1,st.second},{st.first+1,st.second},{st.first,st.second+1},{st.first,st.second-1}};
    vector<pair<int,int>> ans;
    for (auto nei:V) {
        if (bounds(nei) && gval(nei)==0) {
            ans.push_back(nei);
        }
    }
    return ans;
}

signed main() {
    if (debug) freopen("input.txt","r",stdin);
    if (debug) freopen("output.txt","w",stdout);
    cin >> n >> s;
    dist=vector<vector<int>>(n,vector<int>(n,INF));
    grid=vector<vector<int>>(n,vector<int>(n,-1));
    vector<vector<int>> proc(n,vector<int>(n,0));
    vector<pair<int,int>> hives;
    deque<pair<int,int>> visited;
    for (int i=0; i<n; i++) {
        string st;
        cin >> st;
        //if(debug) cout << st << endl;
        for (int j=0; j<n; j++) {
            //if(debug) cout << i <<" " << j << " " << st[j] << endl;
            int ans;
            if (st[j]=='G') {
                ans=0;
            }
            else if (st[j]=='M') {
                ans=0;
                start={i,j};
            }
            else if (st[j]=='D') {
                ans=2;
                finish={i,j};
            }
            else if (st[j]=='T') {
                ans=1;
                
            }
            else {
                //assert(st[j]=='H');
                ans=3;
                hives.push_back({i,j});
                dist[i][j] = 0;
                visited.push_back({i,j});
            }
            grid[i][j] = ans;
            //if(debug) cout << i << " " << j << endl;
        }
    }
    //a cell is available to bees if the cell is 0 or 3, 3 denotes starting hives
    //a cell is available to mecho if the dist condition holds and the cell isn't a tree
    while (visited.size()) {
        pair<int,int> fi=visited[0];
        visited.pop_front();
        if (proc[fi.first][fi.second]) {
            continue;
        }
        proc[fi.first][fi.second] = 1;
        for (auto j:adjlistbee(fi)) {
            dist[j.first][j.second] = min(dist[j.first][j.second],dist[fi.first][fi.second]+1);
            visited.push_back(j);
        }
    }
    if(debug) cout << "DISTS"<< endl;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            //cout << dist[i][j] <<" ";
        }
        if(debug) cout << endl;
    }
    


    int l=0;
    int r=n*3;
    while (l<r) {
        int m=(l+r)/2;
        if (!BSTA(m)) {
            l=l;
            r=m;
        }
        else {
            l=m+1;
            r=r;
        }
    }
    if (l==0 && !BSTA(l)) {
        cout << -1 << endl;
        return 0;
    }
    if (l>0 && !BSTA(l)) {
        l--;
    }
    if (BSTA(l+1)) {
        l++;
    }
    if (l==0 && !BSTA(l)) {
        if(debug) cout << -1 << endl;
        return 0;
    }
    cout << l << endl;

}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:86:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     if (debug) freopen("input.txt","r",stdin);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:87:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     if (debug) freopen("output.txt","w",stdout);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 39 / 100