| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 677906 |
2023-01-04T15:19:50 Z |
vjudge1 |
Golf (JOI17_golf) |
C++17 |
|
0 ms |
324 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i, n) for(int i=(n); i>=1; i--)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define SQ(x) (x)*(x)
#define f first
#define s second
#define pii pair<int, int>
#define endl '\n'
#define pb push_back
const ll mod = 1e9+7;
const ll maxn = 1005;
const ll inf = (1ll<<60);
const ll iinf = 2e9;
ll pw(ll x, ll p){
ll ret=1;
while(p>0){
if (p&1){
ret*=x;
ret%=mod;
}
x*=x;
x%=mod;
p>>=1;
}
return ret;
}
ll inv(ll x){
return pw(x, mod-2);
}
int dis[maxn][maxn];
bool occ[maxn][maxn];
vector<int> dx={1, 0, -1, 0};
vector<int> dy={0, 1, 0, -1};
bool ban[maxn][maxn][4]; // 0 is right, 1 is up, 2 is left, 3 is down
struct rect{
int vl, vr;
int hd, hu;
};
int N, M;
bool oof(pii a){
if (a.f>N||a.f<=0||a.s>M||a.s<=0) return 1;
return 0;
}
signed main(){
//ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int s, t, u, v; cin>>s>>t>>u>>v;
vector<int> px, py;
px.pb(s);
px.pb(u);
py.pb(t);
py.pb(v);
int n; cin>>n;
vector<rect> vc(n);
REP(i, n){
cin>>vc[i].vl>>vc[i].vr>>vc[i].hd>>vc[i].hu;
px.pb(vc[i].vl);
px.pb(vc[i].vr);
py.pb(vc[i].hd);
py.pb(vc[i].hu);
}
sort(ALL(px));
px.erase(unique(ALL(px)), px.end());
sort(ALL(py));
N=SZ(px); M=SZ(py);
py.erase(unique(ALL(py)), py.end());
s=lower_bound(ALL(px), s)-px.begin()+1;
u=lower_bound(ALL(px), u)-px.begin()+1;
t=lower_bound(ALL(py), t)-py.begin()+1;
v=lower_bound(ALL(py), v)-py.begin()+1;
REP(i, n){
vc[i].vl=lower_bound(ALL(px), vc[i].vl)-px.begin()+1;
vc[i].vr=lower_bound(ALL(px), vc[i].vr)-px.begin()+1;
vc[i].hd=lower_bound(ALL(py), vc[i].hd)-py.begin()+1;
vc[i].hu=lower_bound(ALL(py), vc[i].hu)-py.begin()+1;
FOR(j, vc[i].hd+1, vc[i].hu){
ban[vc[i].vl][j][0]=1;
ban[vc[i].vr][j][2]=1;
}
FOR(j, vc[i].vl+1, vc[i].vr){
ban[j][vc[i].hd][1]=1;
ban[j][vc[i].hu][3]=1;
}
}
queue<pii> qu;
qu.push({s, t});
dis[s][t]=0;
REP1(i, N){
REP1(j, M){
dis[i][j]=iinf;
}
}
while(qu.size()){
pii x=qu.front();
qu.pop();
cout<<x.f<<' '<<x.s<<endl;
if (occ[x.f][x.s]) continue;
occ[x.f][x.s]=1;
pii og=x;
REP(j, 4){
x=og;
while(1){
if (ban[x.f][x.s][j]) break;
x.f+=dx[j];
x.s+=dy[j];
if (oof(x)) break;
if (occ[x.f][x.s]) break;
dis[x.f][x.s]=min(dis[x.f][x.s], dis[og.f][og.s]+1);
qu.push({x.f, x.s});
}
}
}
cout<<dis[3][4]<<endl;
cout<<dis[u][v]<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
