Submission #103946

#	Time	Username	Problem	Language	Result	Execution time	Memory
103946		Bodo171	Golf (JOI17_golf)	C++14	30 / 100	577 ms	187828 KiB

golf

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <map>
using namespace std;
const int kmax=100005;
const int nmax=2010;
struct state
{
    int l,c,dir;
};
vector<state> L[4*nmax];
vector<int> norm_x,norm_y;
map<int,int> mX,mY;
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 cateX,cateY;
void normalize()
{
    norm_x.push_back(-1);
    sort(norm_x.begin(),norm_x.end());
    for(i=1;i<norm_x.size();i++)
        if(norm_x[i]!=norm_x[i-1])
           {mX[norm_x[i]]=++cateX;}

    norm_y.push_back(-1);
    sort(norm_y.begin(),norm_y.end());
    for(i=1;i<norm_y.size();i++)
        if(norm_y[i]!=norm_y[i-1])
           {mY[norm_y[i]]=++cateY;}
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>l1>>c1>>l2>>c2;
    l1++,c1++,l2++,c2++;
    norm_x.push_back(l1);norm_x.push_back(l2);
    norm_y.push_back(c1);norm_y.push_back(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));
        norm_x.push_back(X1[i]);norm_x.push_back(X2[i]);
        norm_y.push_back(Y1[i]);norm_y.push_back(Y2[i]);
    }
    norm_x.push_back(1);norm_x.push_back(n);
    norm_y.push_back(1);norm_y.push_back(n);
    normalize();
    n=max(cateX,cateY);
    l1=mX[l1];l2=mX[l2];c1=mY[c1];c2=mY[c2];
   // cout<<l1<<' '<<l2<<' '<<c1<<' '<<c2<<' '<<n<<"ham\n";
    for(i=1;i<=k;i++)
    {
        X1[i]=mX[X1[i]];X2[i]=mX[X2[i]];
        Y1[i]=mY[Y1[i]];Y2[i]=mY[Y2[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 (stderr)

golf.cpp: In function 'void bfs()':
golf.cpp:44:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int it=0;it<L[cost].size();it++)
                      ~~^~~~~~~~~~~~~~~
golf.cpp: In function 'void normalize()':
golf.cpp:66:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1;i<norm_x.size();i++)
             ~^~~~~~~~~~~~~~
golf.cpp:72:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1;i<norm_y.size();i++)
             ~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70