| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 294301 |
2020-09-08T19:04:03 Z |
patrikpavic2 |
Golf (JOI17_golf) |
C++17 |
|
206 ms |
149500 KB |
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef pair < int, int > pt;
const int N = 2e3 + 50;
int n, s_x, s_y, t_x, t_y;
int A[N], B[N], C[N], D[N], dis[N][N], zabD[N][N], zabR[N][N];
int bio[N][N][4];
vector < int > sazx, sazy;
const int px[4] = {1, -1, 0, 0};
const int py[4] = {0, 0, 1, -1};
int nadi(int x, vector < int > &v){
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
int main(){
memset(dis, -1, sizeof(dis));
scanf("%d%d%d%d%d", &s_x, &s_y, &t_x, &t_y, &n);
sazx.PB(s_x); sazx.PB(t_x);
sazy.PB(s_y); sazy.PB(t_y);
for(int i = 0;i < n;i++){
scanf("%d%d%d%d", A + i, B + i, C + i, D + i);
sazx.PB(A[i]); sazx.PB(B[i]);
sazy.PB(C[i]); sazy.PB(D[i]);
}
sort(sazx.begin(), sazx.end());
sort(sazy.begin(), sazy.end());
sazx.erase(unique(sazx.begin(), sazx.end()), sazx.end());
sazy.erase(unique(sazy.begin(), sazy.end()), sazy.end());
s_x = nadi(s_x, sazx); t_x = nadi(t_x, sazx);
s_y = nadi(s_y, sazy); t_y = nadi(t_y, sazy);
for(int i = 0;i < n;i++){
A[i] = nadi(A[i], sazx); B[i] = nadi(B[i], sazx);
C[i] = nadi(C[i], sazy); D[i] = nadi(D[i], sazy);
}
for(int i = 0;i < n;i++){
int kod = i + 1;
if(C[i] + 1 < D[i]){
zabD[A[i]][C[i] + 1] += kod;
zabD[A[i]][D[i]] -= kod;
zabD[B[i]][C[i] + 1] -= kod;
zabD[B[i]][D[i]] += kod;
}
if(A[i] + 1 < B[i]){
zabR[A[i] + 1][C[i]] += kod;
zabR[A[i] + 1][D[i]] -= kod;
zabR[B[i]][C[i]] -= kod;
zabR[B[i]][D[i]] += kod;
}
}
for(int i = 0;i < N;i++){
for(int j = 1;j < N;j++){
zabD[i][j] += zabD[i][j - 1];
zabR[i][j] += zabR[i][j - 1];
}
}
for(int i = 1;i < N;i++){
for(int j = 0;j < N;j++){
zabD[i][j] += zabD[i - 1][j];
zabR[i][j] += zabR[i - 1][j];
}
}
queue < pt > Q;
Q.push({s_x, s_y}); dis[s_x][s_y] = 0;
for(;!Q.empty();Q.pop()){
int x = Q.front().X, y = Q.front().Y;
int nx = x, ny = y;
while(nx < N && !zabD[nx][ny] && (dis[nx + 1][ny] == -1 || dis[x][y] + 1 == dis[nx + 1][ny]) && !bio[nx + 1][ny][0]){
nx++;
if(dis[nx][ny] == -1){
dis[nx][ny] = dis[x][y] + 1;
Q.push({nx, ny});
}
bio[nx][ny][0] = 1;
}
nx = x, ny = y;
while(nx > 0 && !zabD[nx - 1][ny] && (dis[nx - 1][ny] == -1 || dis[x][y] + 1 == dis[nx - 1][ny]) && !bio[nx - 1][ny][1]){
nx++;
if(dis[nx][ny] == -1){
dis[nx][ny] = dis[x][y] + 1;
Q.push({nx, ny});
}
bio[nx][ny][1] = 1;
}
nx = x, ny = y;
while(ny < N && !zabR[nx][ny] && (dis[nx][ny + 1] == -1 || dis[x][y] + 1 == dis[nx][ny + 1]) && !bio[nx][ny + 1][2]){
ny++;
if(dis[nx][ny] == -1){
dis[nx][ny] = dis[x][y] + 1;
Q.push({nx, ny});
}
bio[nx][ny][2] = 1;
}
nx = x, ny = y;
while(ny > 0 && !zabR[nx][ny - 1] && (dis[nx][ny - 1] == -1 || dis[x][y] + 1 == dis[nx][ny - 1]) && !bio[nx][ny - 1][3]){
ny--;
if(dis[nx][ny] == -1){
dis[nx][ny] = dis[x][y] + 1;
Q.push({nx, ny});
}
bio[nx][ny][3] = 1;
}
}
printf("%d\n", dis[t_x][t_y]);
return 0;
}
Compilation message
golf.cpp: In function 'int main()':
golf.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
32 | scanf("%d%d%d%d%d", &s_x, &s_y, &t_x, &t_y, &n);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:36:8: 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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
149500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
149500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
149500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
