oj.uz

Submission #236156

# Submission time Handle Problem Language Result Execution time Memory
236156 2020-05-31T10:10:21 Z topovik Portal (COCI17_portal) C++14
120 / 120
 240 ms 11640 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;

typedef long long ll;

const ll oo = 1e9+7;
const ll N = 500;

pair<int,int> lf[N][N],rg[N][N],up[N][N],dn[N][N];

int kol[N][N];
bool mrk[N][N],used[N][N];

int main()
{
    int n,m;
    cin>>n>>m;
    string a[n];
    for (int i=0; i<n; i++) cin>>a[i];

    for (int i=0; i<n; i++)
    {
        int r=1;
        for (int j=0; j<m; j++)
        {
            lf[i][j]={i,j-r};
            if (a[i][j]=='#') r=0;
            else              r++;
        }
        r=1;
        for (int j=m-1; j>=0; j--)
        {
            rg[i][j]={i,j+r};
            if (a[i][j]=='#') r=0;
            else              r++;
        }
    }

    for (int j=0; j<m; j++)
    {
        int r=1;
        for (int i=0; i<n; i++)
        {
            up[i][j]={i-r,j};
            if (a[i][j]=='#') r=0;
            else              r++;
        }
        r=1;
        for (int i=n-1; i>=0; i--)
        {
            dn[i][j]={i+r,j};
            if (a[i][j]=='#') r=0;
            else              r++;
        }
    }
    queue<tuple<int,int,int> > q;
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
          if (a[i][j]=='#') q.push(make_tuple(i,j,0)),mrk[i][j]=1;
    while (q.size()>0)
    {
        tuple <int,int,int> c=q.front();
        kol[get<0>(c)][get<1>(c)]=get<2>(c);
        q.pop();
        for (int i=-1; i<2; i+=2)
        {
            int sx=get<0>(c)+i;
            int sy=get<1>(c);
            if (sx>0 && sy>0 && sx<n && sy<m && !mrk[sx][sy]) q.push(make_tuple(sx,sy,get<2>(c)+1)),mrk[sx][sy]=1;
        }
        for (int i=-1; i<2; i+=2)
        {
            int sx=get<0>(c);
            int sy=get<1>(c)+i;
            if (sx>0 && sy>0 && sx<n && sy<m && !mrk[sx][sy]) q.push(make_tuple(sx,sy,get<2>(c)+1)),mrk[sx][sy]=1;
        }
    }
    multiset <tuple<int,int,int> > que;
    int sx=0,sy=0,ex=0,ey=0;
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
          if (a[i][j]=='C') sx=i,sy=j;
          else
          if (a[i][j]=='F') ex=i,ey=j;
    que.insert(make_tuple(0,sx,sy));
    bool g=1;
    while (que.size()>0)
    {
        int x=get<1>(*que.begin());
        int y=get<2>(*que.begin());
        int kl=get<0>(*que.begin());
        que.erase(que.begin());
        while (used[x][y] && que.size()>0)
        {
        x=get<1>(*que.begin());
        y=get<2>(*que.begin());
        kl=get<0>(*que.begin());
        que.erase(que.begin());
        }
        if (used[x][y]) break;
        used[x][y]=1;
        if (x==ex && y==ey) {cout<<kl<<endl;g=0;break;}
        que.insert(make_tuple(kl+kol[x][y],up[x][y].f,up[x][y].s));
        que.insert(make_tuple(kl+kol[x][y],dn[x][y].f,dn[x][y].s));
        que.insert(make_tuple(kl+kol[x][y],lf[x][y].f,lf[x][y].s));
        que.insert(make_tuple(kl+kol[x][y],rg[x][y].f,rg[x][y].s));
        for (int i=-1; i<2; i+=2)
        {
            int sx=x+i;
            int sy=y;
            if (sx>0 && sy>0 && sx<n && sy<m && !used[sx][sy] && a[sx][sy]!='#') que.insert(make_tuple(kl+1,sx,sy));
        }
        for (int i=-1; i<2; i+=2)
        {
            int sx=x;
            int sy=y+i;
            if (sx>0 && sy>0 && sx<n && sy<m && !used[sx][sy] && a[sx][sy]!='#') que.insert(make_tuple(kl+1,sx,sy));
        }
    }
    if (g) cout<<"nemoguce\n";
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 640 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4224 KB Output is correct
2 Correct 8 ms 2304 KB Output is correct
3 Correct 24 ms 2304 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3584 KB Output is correct
2 Correct 11 ms 4480 KB Output is correct
3 Correct 32 ms 2816 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 8652 KB Output is correct
2 Correct 36 ms 5924 KB Output is correct
3 Correct 84 ms 6640 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 10240 KB Output is correct
2 Correct 29 ms 10872 KB Output is correct
3 Correct 119 ms 7220 KB Output is correct
4 Correct 98 ms 8564 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 11640 KB Output is correct
2 Correct 35 ms 11384 KB Output is correct
3 Correct 185 ms 11264 KB Output is correct
4 Correct 194 ms 11256 KB Output is correct