oj.uz

Submission #422364

# Submission time Handle Problem Language Result Execution time Memory
422364 2021-06-10T04:47:43 Z Amylopectin Robots (APIO13_robots) C++14
100 / 100
 628 ms 60112 KB 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int mxn = 510,mxm = 90,mxi = 1e9 + 10,mxp = 3e5 + 10,dn[4] = {-1,0,1,0},dm[4] = {0,1,0,-1};
struct we
{
    int nn,mm,dis;
};
bool cmp(const struct we &l,const struct we &r)
{
    return l.dis < r.dis;
}
queue <struct we> qu;
struct we st[mxn] = {};
char s[mxn][mxn] = {};
int di[mxm][mxn][mxn] = {},u[mxn][mxn] = {};
struct we pa[mxn][mxn][4] = {},pli[mxp] = {};
int fima(int l,int r)
{
    if(l > r)
        return l;
    return r;
}
int fimi(int l,int r)
{
    if(l < r)
        return l;
    return r;
}
int main()
{
    int i,j,n,m,ro,cn,cm,fn,fm,cva,k,o,p,f,t,af,cdir,of,cou,cru,cdi,fdi,uc,cmi = mxi;
    scanf("%d %d %d",&ro,&m,&n);
    for(i=0; i<n; i++)
    {
        scanf("%s",&s[i]);
        for(j=0; j<m; j++)
        {
            if(s[i][j] > '0' && s[i][j] <= '9')
            {
                cva = s[i][j] - '1';
                st[cva] = {i,j,0};
            }
        }
    }
    cou = 0;
    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            for(k=0; k<4; k++)
            {
                cn = i;
                cm = j;
                cdir = k;
                cou ++;
                while(1)
                {
                    of = 0;
                    while(1)
                    {
                        fn = cn+dn[cdir];
                        fm = cm+dm[cdir];
                        if(fn < 0 || fn >= n || fm < 0 || fm >= m || s[fn][fm] == 'x')
                        {
                            of = 1;
                            break;
                        }
                        cn = fn;
                        cm = fm;
                        if(s[cn][cm] == 'C')
                        {
                            cdir = (cdir + 1) % 4;
                            break;
                        }
                        if(s[cn][cm] == 'A')
                        {
                            cdir = (cdir + 3) % 4;
                            break;
                        }
                    }
                    if(u[cn][cm] == cou)
                    {
                        break;
                    }
                    u[cn][cm] = cou;
                    if(of == 1)
                    {
                        break;
                    }
                }
                pa[i][j][k] = {cn,cm,0};
                if(of == 0)
                {
                    pa[i][j][k].dis = -1;
                }
            }
        }
    }
//    uc = 0;
    for(i=0; i<ro; i++)
    {
        for(j=i; j>=0; j--)
        {
            af = j*ro + i;
            for(o=0; o<n; o++)
            {
                for(p=0; p<m; p++)
                {
                    di[af][o][p] = mxi;
                    u[o][p] = 0;
                }
            }
            if(j < i)
            {
                for(k=j; k<i; k++)
                {
                    f = j*ro+k;
                    t = (k+1)*ro + i;
                    for(o=0; o<n; o++)
                    {
                        if(di[f][o][p] != mxi)
                        for(p=0; p<m; p++)
                        {
                            if(di[t][o][p] != mxi)
                            {
                                di[af][o][p] = fimi(di[af][o][p], di[f][o][p] + di[t][o][p]);
                            }
                        }
                    }
                }
                cou = 0;
                for(o=0; o<n; o++)
                {
                    for(p=0; p<m; p++)
                    {
                        if(di[af][o][p] != mxi)
                        {
                            pli[cou] = {o,p,di[af][o][p]};
                            cou ++;
                        }
                    }
                }
                cru = 0;
                sort(pli,pli+cou,cmp);
                cdi = pli[0].dis;
                while(pli[cru].dis == cdi && cru < cou)
                {
                    qu.push(pli[cru]);
                    u[pli[cru].nn][pli[cru].mm] = 1;
                    cru ++;
                }
            }
            else
            {
                di[af][st[i].nn][st[i].mm] = 0;
                qu.push({st[i].nn,st[i].mm,0});
                u[st[i].nn][st[i].mm] = 1;
                cou = 0;
                cru = 0;
            }
            while(!qu.empty())
            {
                cn = qu.front().nn;
                cm = qu.front().mm;
                cdi = qu.front().dis;
                qu.pop();
                while(cru < cou && pli[cru].dis == cdi)
                {
                    fn = pli[cru].nn;
                    fm = pli[cru].mm;
                    if(u[fn][fm] == 0)
                    {
                        u[fn][fm] = 1;
                        qu.push(pli[cru]);
                    }
                    cru ++;
                }
                for(k=0; k<4; k++)
                {
                    if(pa[cn][cm][k].dis == -1)
                    {
                        continue;
                    }
                    fn = pa[cn][cm][k].nn;
                    fm = pa[cn][cm][k].mm;
                    if(u[fn][fm] == 1)
                    {
                        continue;
                    }
                    u[fn][fm] = 1;
                    di[af][fn][fm] = cdi+1;
                    qu.push({fn,fm,cdi+1});
                }
            }
        }
    }
    af = 0*ro + ro-1;
    for(o=0; o<n; o++)
    {
        for(p=0; p<m; p++)
        {
            cmi = fimi(cmi,di[af][o][p]);
        }
    }
    if(cmi != mxi)
    {
        printf("%d\n",cmi);
    }
    else
    {
        printf("-1\n");
    }
    return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:39:17: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[510]' [-Wformat=]
   39 |         scanf("%s",&s[i]);
      |                ~^  ~~~~~
      |                 |  |
      |                 |  char (*)[510]
      |                 char*
robots.cpp:35:69: warning: unused variable 'fdi' [-Wunused-variable]
   35 |     int i,j,n,m,ro,cn,cm,fn,fm,cva,k,o,p,f,t,af,cdir,of,cou,cru,cdi,fdi,uc,cmi = mxi;
      |                                                                     ^~~
robots.cpp:35:73: warning: unused variable 'uc' [-Wunused-variable]
   35 |     int i,j,n,m,ro,cn,cm,fn,fm,cva,k,o,p,f,t,af,cdir,of,cou,cru,cdi,fdi,uc,cmi = mxi;
      |                                                                         ^~
robots.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d %d %d",&ro,&m,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%s",&s[i]);
      |         ~~~~~^~~~~~~~~~~~
robots.cpp:125:38: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |                         if(di[f][o][p] != mxi)
      |                            ~~~~~~~~~~^

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 97 ms 33892 KB Output is correct
12 Correct 10 ms 6988 KB Output is correct
13 Correct 60 ms 23340 KB Output is correct
14 Correct 228 ms 33808 KB Output is correct
15 Correct 69 ms 33648 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 97 ms 33892 KB Output is correct
12 Correct 10 ms 6988 KB Output is correct
13 Correct 60 ms 23340 KB Output is correct
14 Correct 228 ms 33808 KB Output is correct
15 Correct 69 ms 33648 KB Output is correct
16 Correct 349 ms 58600 KB Output is correct
17 Correct 628 ms 60100 KB Output is correct
18 Correct 163 ms 59844 KB Output is correct
19 Correct 281 ms 58568 KB Output is correct
20 Correct 442 ms 60112 KB Output is correct