oj.uz

Submission #103946

# Submission time Handle Problem Language Result Execution time Memory
103946 2019-04-03T12:09:13 Z Bodo171 Golf (JOI17_golf) C++14
30 / 100
 577 ms 187828 KB 
#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

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.0 / 10.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 6 ms 768 KB Output is correct
4 Correct 15 ms 3756 KB Output is correct
5 Correct 109 ms 46372 KB Output is correct
6 Correct 81 ms 33580 KB Output is correct
7 Correct 101 ms 35224 KB Output is correct
8 Correct 108 ms 35060 KB Output is correct
9 Correct 91 ms 39948 KB Output is correct
10 Correct 98 ms 38696 KB Output is correct
11 Correct 113 ms 38080 KB Output is correct
12 Correct 87 ms 37652 KB Output is correct
13 Correct 82 ms 32468 KB Output is correct
14 Correct 93 ms 37588 KB Output is correct
15 Correct 46 ms 15512 KB Output is correct
16 Correct 119 ms 51888 KB Output is correct

Subtask #2
20.0 / 20.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 6 ms 768 KB Output is correct
4 Correct 15 ms 3756 KB Output is correct
5 Correct 109 ms 46372 KB Output is correct
6 Correct 81 ms 33580 KB Output is correct
7 Correct 101 ms 35224 KB Output is correct
8 Correct 108 ms 35060 KB Output is correct
9 Correct 91 ms 39948 KB Output is correct
10 Correct 98 ms 38696 KB Output is correct
11 Correct 113 ms 38080 KB Output is correct
12 Correct 87 ms 37652 KB Output is correct
13 Correct 82 ms 32468 KB Output is correct
14 Correct 93 ms 37588 KB Output is correct
15 Correct 46 ms 15512 KB Output is correct
16 Correct 119 ms 51888 KB Output is correct
17 Correct 487 ms 179220 KB Output is correct
18 Correct 523 ms 174744 KB Output is correct
19 Correct 497 ms 175336 KB Output is correct
20 Correct 543 ms 170624 KB Output is correct
21 Correct 577 ms 187828 KB Output is correct
22 Correct 511 ms 176652 KB Output is correct
23 Correct 513 ms 174668 KB Output is correct
24 Correct 532 ms 170148 KB Output is correct
25 Correct 456 ms 170472 KB Output is correct
26 Correct 467 ms 161520 KB Output is correct
27 Correct 56 ms 21160 KB Output is correct
28 Correct 144 ms 61640 KB Output is correct
29 Correct 160 ms 63188 KB Output is correct

Subtask #3
0 / 70.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 6 ms 768 KB Output is correct
4 Correct 15 ms 3756 KB Output is correct
5 Correct 109 ms 46372 KB Output is correct
6 Correct 81 ms 33580 KB Output is correct
7 Correct 101 ms 35224 KB Output is correct
8 Correct 108 ms 35060 KB Output is correct
9 Correct 91 ms 39948 KB Output is correct
10 Correct 98 ms 38696 KB Output is correct
11 Correct 113 ms 38080 KB Output is correct
12 Correct 87 ms 37652 KB Output is correct
13 Correct 82 ms 32468 KB Output is correct
14 Correct 93 ms 37588 KB Output is correct
15 Correct 46 ms 15512 KB Output is correct
16 Correct 119 ms 51888 KB Output is correct
17 Correct 487 ms 179220 KB Output is correct
18 Correct 523 ms 174744 KB Output is correct
19 Correct 497 ms 175336 KB Output is correct
20 Correct 543 ms 170624 KB Output is correct
21 Correct 577 ms 187828 KB Output is correct
22 Correct 511 ms 176652 KB Output is correct
23 Correct 513 ms 174668 KB Output is correct
24 Correct 532 ms 170148 KB Output is correct
25 Correct 456 ms 170472 KB Output is correct
26 Correct 467 ms 161520 KB Output is correct
27 Correct 56 ms 21160 KB Output is correct
28 Correct 144 ms 61640 KB Output is correct
29 Correct 160 ms 63188 KB Output is correct
30 Runtime error 375 ms 43720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -