Submission #236178

#	Time	Username	Problem	Language	Result	Execution time	Memory
236178		nicolaalexandra	Mecho (IOI09_mecho)	C++14	37 / 100	246 ms	8696 KiB

mecho

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

char s[DIM];
int a[DIM][DIM],b[DIM][DIM],dist[DIM][DIM],f[DIM];
deque <pair<int,int> > c,aux,d;
int di[] = {-1,1,0,0};
int dj[] = {0,0,-1,1};
int n,nr,i,j,xstart,ystart,xfin,yfin;
inline int inmat (int i, int j){
    if (i >= 1 && j >= 1 && i <= n && j <= n)
        return 1;
    return 0;
}
int verif (int val){

    /// mai intai vad cat se extind albinele dupa val secunde
    c.clear();
    memset (f,0,sizeof f);
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++){
            b[i][j] = a[i][j];
            if (a[i][j] == 1)
                c.push_back(make_pair(i,j));
        }

    for (i=1;i<=val;i++){
        aux.clear();
        for (auto it : c){
            int ic = it.first, jc = it.second;
            for (int dir=0;dir<=3;dir++){
                int iv = ic + di[dir];
                int jv = jc + dj[dir];
                if (inmat (iv,jv) && b[iv][jv] == 0){
                    aux.push_back(make_pair(iv,jv));
                    b[iv][jv] = 1;
                }}}
        c = aux;
        f[i] = 1;
    }

    if (b[xstart][ystart])
        return 0;

    /// d - lista cu toate locurile in care pot sa ajung pana la secunda asta
    memset (dist,0,sizeof dist);
    d.clear();
    d.push_back(make_pair(xstart,ystart));
    dist[xstart][ystart] = 1;

    while (!d.empty()){
        int ic = d.front().first;
        int jc = d.front().second;
        d.pop_front();

        if (dist[ic][jc] % nr == 0 && !f[dist[ic][jc] / nr + val]){
            /// inseamna ca a mai trecut un minut si trb sa avansez cu albinele
            f[dist[ic][jc] / nr + val] = 1;
            aux.clear();
            for (auto it : c){
                int i = it.first, j = it.second;
                for (int dir=0;dir<=3;dir++){
                    int iv = i + di[dir];
                    int jv = j + dj[dir];
                    if (inmat(iv,jv) && b[iv][jv] == 0){
                        aux.push_back(make_pair(iv,jv));
                        b[iv][jv] = 1;
                    }}}
            c = aux;
        }

        for (int dir=0;dir<=3;dir++){
            int iv = ic + di[dir];
            int jv = jc + dj[dir];
            if (inmat (iv,jv) && (b[iv][jv] == 0 || b[iv][jv] == 3) && !dist[iv][jv]){
                if (iv == xfin && jv == yfin) /// am reusit sa ajung
                    return 1;

                dist[iv][jv] = 1 + dist[ic][jc];
                d.push_back(make_pair(iv,jv));
            }}}

    return 0;

}


int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>nr;
    for (i=1;i<=n;i++){
        cin>>s+1;
        for (j=1;j<=n;j++){
            if (s[j] == 'T')
                a[i][j] = 2;
            if (s[j] == 'M'){
                xstart = i, ystart = j;
                //a[i][j] = 4;
            }
            if (s[j] == 'D'){
                xfin = i, yfin = j;
                a[i][j] = 3;
            }
            if (s[j] == 'H')
                a[i][j] = 1;
        }
    }
    /*for (i=1;i<=n;i++,cout<<endl)
        for (j=1;j<=n;j++)
            cout<<a[i][j]<<" ";
*/
    int st = 0, dr = n, sol = 0;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif (mid)){
            sol = mid;
            st = mid+1;
        } else dr = mid-1;
    }

    cout<<sol;

    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:96:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin>>s+1;
              ~^~

• Subtask 1: 37 / 100