oj.uz

Submission #103945

# Submission time Handle Problem Language Result Execution time Memory
103945 2019-04-03T11:54:58 Z Bodo171 Golf (JOI17_golf) C++14
10 / 100
 314 ms 84076 KB 
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
const int kmax=100005;
const int nmax=2010;
struct state
{
    int l,c,dir;
};
vector<state> L[4*nmax];
int X1[kmax],X2[nmax],Y1[kmax],Y2[kmax];
int v[nmax][nmax];
int d[nmax][nmax][4];
int d1[]={-1,0,1,0};
int d2[]={0,-1,0,1};
int n,k,i,j,dir,l1,c1,l2,c2,li,ci,di,lf,cf,df;
void prp(int l,int c,int dd,int cost_nou)
{
    if(l<1||c<1||l>n||c>n) return;
    if(cost_nou<d[l][c][dd])
    {
        d[l][c][dd]=cost_nou;
        L[cost_nou].push_back({l,c,dd});
    }
}
void bfs()
{
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
           for(dir=0;dir<4;dir++)
                d[i][j][dir]=(1<<30);
    for(int i=0;i<4;i++)
    {
        L[1].push_back({l1,c1,i});
        d[l1][c1][i]=1;
    }
    for(int cost=0;cost<=4*n;cost++)
    {
        for(int it=0;it<L[cost].size();it++)
        {
            li=L[cost][it].l;ci=L[cost][it].c;di=L[cost][it].dir;
            if(cost==d[li][ci][di])
            {
                for(df=0;df<4;df++)
                {
                    lf=li+d1[df];cf=ci+d2[df];
                    if(!((1<<df)&v[li][ci]))
                    {
                        prp(lf,cf,df,cost+(di!=df));
                    }
                }
            }
        }
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>l1>>c1>>l2>>c2;
    l1++,c1++,l2++,c2++;
    n=max(l1+1,l2+1);
    n=max(n,max(c1+1,c2+1));
    cin>>k;
    for(i=1;i<=k;i++)
    {
        cin>>X1[i]>>X2[i]>>Y1[i]>>Y2[i];
        X1[i]++;Y1[i]++;X2[i]++;Y2[i]++;
        n=max(n,max(X1[i]+1,X2[i]+1));
        n=max(n,max(Y1[i]+1,Y2[i]+1));
    }
    for(i=1;i<=k;i++)
    {
        for(j=Y1[i]+1;j<=Y2[i]-1;j++)
        {
            v[X1[i]][j]|=4;
            v[X2[i]][j]|=1;
        }
        for(j=X1[i]+1;j<=X2[i]-1;j++)
        {
            v[j][Y1[i]]|=8;
            v[j][Y2[i]]|=2;
        }
    }
    /*for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(l1==i&&c1==j) cout<<"s ";
            else if(l2==i&&c2==j) cout<<"e ";
            else cout<<v[i][j]<<' ';
        }
        cout<<'\n';
    }*/
    bfs();
    int ans=(1<<30);
    for(int i=0;i<4;i++)
        ans=min(ans,d[l2][c2][i]);
    cout<<ans;
    return 0;
}

Compilation message

golf.cpp: In function 'void bfs()':
golf.cpp:40:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int it=0;it<L[cost].size();it++)
                      ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 61076 KB Output is correct
2 Correct 167 ms 84076 KB Output is correct
3 Correct 171 ms 72660 KB Output is correct
4 Correct 96 ms 49424 KB Output is correct
5 Correct 108 ms 46828 KB Output is correct
6 Correct 97 ms 43276 KB Output is correct
7 Correct 106 ms 41684 KB Output is correct
8 Correct 135 ms 44404 KB Output is correct
9 Correct 99 ms 44876 KB Output is correct
10 Correct 104 ms 44432 KB Output is correct
11 Correct 115 ms 50532 KB Output is correct
12 Correct 106 ms 43564 KB Output is correct
13 Correct 106 ms 42960 KB Output is correct
14 Correct 131 ms 47840 KB Output is correct
15 Correct 134 ms 58276 KB Output is correct
16 Correct 207 ms 78964 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 61076 KB Output is correct
2 Correct 167 ms 84076 KB Output is correct
3 Correct 171 ms 72660 KB Output is correct
4 Correct 96 ms 49424 KB Output is correct
5 Correct 108 ms 46828 KB Output is correct
6 Correct 97 ms 43276 KB Output is correct
7 Correct 106 ms 41684 KB Output is correct
8 Correct 135 ms 44404 KB Output is correct
9 Correct 99 ms 44876 KB Output is correct
10 Correct 104 ms 44432 KB Output is correct
11 Correct 115 ms 50532 KB Output is correct
12 Correct 106 ms 43564 KB Output is correct
13 Correct 106 ms 42960 KB Output is correct
14 Correct 131 ms 47840 KB Output is correct
15 Correct 134 ms 58276 KB Output is correct
16 Correct 207 ms 78964 KB Output is correct
17 Runtime error 13 ms 1000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 61076 KB Output is correct
2 Correct 167 ms 84076 KB Output is correct
3 Correct 171 ms 72660 KB Output is correct
4 Correct 96 ms 49424 KB Output is correct
5 Correct 108 ms 46828 KB Output is correct
6 Correct 97 ms 43276 KB Output is correct
7 Correct 106 ms 41684 KB Output is correct
8 Correct 135 ms 44404 KB Output is correct
9 Correct 99 ms 44876 KB Output is correct
10 Correct 104 ms 44432 KB Output is correct
11 Correct 115 ms 50532 KB Output is correct
12 Correct 106 ms 43564 KB Output is correct
13 Correct 106 ms 42960 KB Output is correct
14 Correct 131 ms 47840 KB Output is correct
15 Correct 134 ms 58276 KB Output is correct
16 Correct 207 ms 78964 KB Output is correct
17 Runtime error 13 ms 1000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -