oj.uz

Submission #590693

# Submission time Handle Problem Language Result Execution time Memory
590693 2022-07-06T08:49:21 Z 조영욱(#8414) Golf (JOI17_golf) C++17
10 / 100
 119 ms 77872 KB 
#include <bits/stdc++.h>
using namespace std;

int s,t,u,v;
int n;
int a[1000];
int b[1000];
int c[1000];
int d[1000];
vector<int> px;
vector<int> py;
bool alive[2002][2002];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
typedef pair<int,int> P;
typedef pair<P,int> Pi;
int dist[2002][2002][4];

bool valid(int x,int y) {
    return x>=0&&x<px.size()&&y>=0&&y<py.size()&&alive[x][y];
}

int main(void) {
    memset(alive,-1,sizeof(alive));
    scanf("%d %d %d %d",&s,&t,&u,&v);
    s*=2;
    t*=2;
    u*=2;
    v*=2;
    px.push_back(s);
    py.push_back(t);
    px.push_back(u);
    py.push_back(v);
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
        a[i]*=2;
        b[i]*=2;
        c[i]*=2;
        d[i]*=2;
        px.push_back(a[i]);
        px.push_back(b[i]);
        py.push_back(c[i]);
        py.push_back(d[i]);
        px.push_back(a[i]+1);
        px.push_back(b[i]-1);
        py.push_back(c[i]+1);
        py.push_back(d[i]-1);
    }
    sort(px.begin(),px.end());
    px.erase(unique(px.begin(),px.end()),px.end());
    sort(py.begin(),py.end());
    py.erase(unique(py.begin(),py.end()),py.end());
    s=lower_bound(px.begin(),px.end(),s)-px.begin();
    t=lower_bound(py.begin(),py.end(),t)-py.begin();
    u=lower_bound(px.begin(),px.end(),u)-px.begin();
    v=lower_bound(py.begin(),py.end(),v)-py.begin();
    for(int i=0;i<n;i++) {
        a[i]=lower_bound(px.begin(),px.end(),a[i])-px.begin();
        b[i]=lower_bound(px.begin(),px.end(),b[i])-px.begin();
        c[i]=lower_bound(py.begin(),py.end(),c[i])-py.begin();
        d[i]=lower_bound(py.begin(),py.end(),d[i])-py.begin();
        for(int x=a[i]+1;x<b[i];x++) {
            for(int y=c[i]+1;y<d[i];y++) {
                //printf("%d %d\n",x,y);
                alive[x][y]=false;
            }
        }
    }
    //printf("%d %d %d %d\n",s,t,u,v);
    memset(dist,-1,sizeof(dist));
    deque<Pi> dq;
    for(int i=0;i<4;i++) {
        dq.push_front(Pi(P(s,t),i));
        dist[s][t][i]=0;
    }
    while (!dq.empty()) {
        Pi now=dq.front();
        dq.pop_front();
        int x=now.first.first;
        int y=now.first.second;
        int d=now.second;
        int nx=x+dx[d];
        int ny=y+dy[d];
        if (!valid(nx,ny)) {
            continue;
        }
        for(int i=0;i<4;i++) {
int nd=dist[x][y][d]+(d!=i);
            if (dist[nx][ny][i]==-1||dist[nx][ny][i]>nd) {
                if (d==i) {
                    dq.push_front(Pi(P(nx,ny),i));
                    dist[nx][ny][i]=dist[x][y][d];
                }
                else {
                    dq.push_back(Pi(P(nx,ny),i));
                    dist[nx][ny][i]=dist[x][y][d]+1;
                }
            }
        }
    }
    int ret=1e9;
    for(int i=0;i<4;i++) {
        ret=min(ret,dist[u][v][i]);
    }
    printf("%d",ret+1);
}

Compilation message

golf.cpp: In function 'bool valid(int, int)':
golf.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     return x>=0&&x<px.size()&&y>=0&&y<py.size()&&alive[x][y];
      |                  ~^~~~~~~~~~
golf.cpp:20:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     return x>=0&&x<px.size()&&y>=0&&y<py.size()&&alive[x][y];
      |                                     ~^~~~~~~~~~
golf.cpp: In function 'int main()':
golf.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d %d %d %d",&s,&t,&u,&v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
golf.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 66900 KB Output is correct
2 Correct 25 ms 66900 KB Output is correct
3 Correct 27 ms 66928 KB Output is correct
4 Correct 36 ms 67900 KB Output is correct
5 Correct 107 ms 77872 KB Output is correct
6 Correct 110 ms 73580 KB Output is correct
7 Correct 110 ms 73812 KB Output is correct
8 Correct 106 ms 73072 KB Output is correct
9 Correct 98 ms 72472 KB Output is correct
10 Correct 119 ms 74112 KB Output is correct
11 Correct 114 ms 74944 KB Output is correct
12 Correct 118 ms 72064 KB Output is correct
13 Correct 98 ms 73260 KB Output is correct
14 Correct 119 ms 74832 KB Output is correct
15 Correct 45 ms 67148 KB Output is correct
16 Correct 118 ms 67288 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 66900 KB Output is correct
2 Correct 25 ms 66900 KB Output is correct
3 Correct 27 ms 66928 KB Output is correct
4 Correct 36 ms 67900 KB Output is correct
5 Correct 107 ms 77872 KB Output is correct
6 Correct 110 ms 73580 KB Output is correct
7 Correct 110 ms 73812 KB Output is correct
8 Correct 106 ms 73072 KB Output is correct
9 Correct 98 ms 72472 KB Output is correct
10 Correct 119 ms 74112 KB Output is correct
11 Correct 114 ms 74944 KB Output is correct
12 Correct 118 ms 72064 KB Output is correct
13 Correct 98 ms 73260 KB Output is correct
14 Correct 119 ms 74832 KB Output is correct
15 Correct 45 ms 67148 KB Output is correct
16 Correct 118 ms 67288 KB Output is correct
17 Runtime error 8 ms 8532 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 66900 KB Output is correct
2 Correct 25 ms 66900 KB Output is correct
3 Correct 27 ms 66928 KB Output is correct
4 Correct 36 ms 67900 KB Output is correct
5 Correct 107 ms 77872 KB Output is correct
6 Correct 110 ms 73580 KB Output is correct
7 Correct 110 ms 73812 KB Output is correct
8 Correct 106 ms 73072 KB Output is correct
9 Correct 98 ms 72472 KB Output is correct
10 Correct 119 ms 74112 KB Output is correct
11 Correct 114 ms 74944 KB Output is correct
12 Correct 118 ms 72064 KB Output is correct
13 Correct 98 ms 73260 KB Output is correct
14 Correct 119 ms 74832 KB Output is correct
15 Correct 45 ms 67148 KB Output is correct
16 Correct 118 ms 67288 KB Output is correct
17 Runtime error 8 ms 8532 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -