Submission #1199209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199209		alexander707070	Golf (JOI17_golf)	C++20	10 / 100	236 ms	145848 KiB

golf

#include<bits/stdc++.h>
#define MAXN 1007
using namespace std;

const int inf=1e9+7;

struct rect{
    int a,b,c,d;
}s[MAXN];

int k;
pair<int,int> st,et;

int n,m;
vector<int> w;
map<int,int> mp;

bool hor[2007][2007],ver[2007][2007];
int horv[2007][2007],verv[2007][2007];

int num;
vector<int> v[2007*2007];

void compress(){
    w={1,inf};

    w.push_back(st.first);
    w.push_back(et.first);

    for(int i=1;i<=k;i++){
        w.push_back(s[i].a);
        w.push_back(s[i].b);
    }

    sort(w.begin(),w.end());

    for(int i=0;i<w.size();i++){
        if(i==0 or w[i]!=w[i-1])n++;
        mp[w[i]]=n;
    }

    st.first=mp[st.first];
    et.first=mp[et.first];

    for(int i=1;i<=k;i++){
        s[i].a=mp[s[i].a];
        s[i].b=mp[s[i].b];
    }

    w.clear(); mp.clear();
    w={1,inf};

    w.push_back(st.second);
    w.push_back(et.second);

    for(int i=1;i<=k;i++){
        w.push_back(s[i].c);
        w.push_back(s[i].d);
    }

    sort(w.begin(),w.end());

    for(int i=0;i<w.size();i++){
        if(i==0 or w[i]!=w[i-1])m++;
        mp[w[i]]=m;
    }

    st.second=mp[st.second];
    et.second=mp[et.second];

    for(int i=1;i<=k;i++){
        s[i].c=mp[s[i].c];
        s[i].d=mp[s[i].d];
    }
}

queue<int> q;
int dist[2007*2007];
bool vis[2007*2007];

void bfs(){
    q.push(horv[st.first][st.second]);
    q.push(verv[st.first][st.second]);

    vis[horv[st.first][st.second]]=true;
    vis[verv[st.first][st.second]]=true;

    while(!q.empty()){
        for(int i:v[q.front()]){
            if(vis[i])continue;

            vis[i]=true; q.push(i);
            dist[i]=dist[q.front()]+1;
        }

        q.pop();
    }
}

int main(){

    cin>>st.first>>st.second>>et.first>>et.second;
    cin>>k;

    for(int i=1;i<=k;i++){
        cin>>s[i].a>>s[i].b>>s[i].c>>s[i].d;
    }

    compress();

    for(int i=1;i<=k;i++){
        for(int f=s[i].a+1;f<=s[i].b-1;f++){
            for(int t=s[i].c;t<s[i].d;t++)hor[f][t]=true;
        }

        for(int f=s[i].c+1;f<=s[i].d-1;f++){
            for(int t=s[i].a;t<s[i].b;t++)ver[t][f]=true;
        }
    }

    for(int i=1;i<=n;i++)hor[i][m]=true;
    for(int f=1;f<=m;f++)ver[n][f]=true;

    for(int i=1;i<=n;i++){
        int br=0;
        for(int f=1;f<=m;f++){
            if(!hor[i][f]){
                br++; continue;
            }

            num++;
            for(int t=f-br;t<=f;t++)horv[i][t]=num;
            br=0;
        }
    }

    for(int f=1;f<=m;f++){
        int br=0;
        for(int i=1;i<=n;i++){
            if(!ver[i][f]){
                br++; continue;
            }

            num++;
            for(int t=i-br;t<=i;t++)verv[t][f]=num;
            br=0;
        }
    }

    for(int i=1;i<=n;i++){
        for(int f=1;f<=m;f++){
            if(horv[i][f]==0)continue;

            v[horv[i][f]].push_back(verv[i][f]);
            v[verv[i][f]].push_back(horv[i][f]);
        }
    }

    bfs();

    cout<<min(dist[horv[et.first][et.second]] , dist[verv[et.first][et.second]] )+1<<"\n";

    return 0;
}

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