Submission #677912

#	Time	Username	Problem	Language	Result	Execution time	Memory
677912		browntoad	Golf (JOI17_golf)	C++14	10 / 100	3971 ms	1045268 KiB

golf

#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});
    REP1(i, N){
        REP1(j, M){
            dis[i][j]=iinf;
        }
    }
    dis[s][t]=0;
    while(qu.size()){
        pii x=qu.front();
        qu.pop();
        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[u][v]<<endl;
}

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