Submission #3767514

---

Source Code Expand

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


using Edge=int;
using Edges=vector<Edge>;
using Graph=vector<Edges>;

void SSC(Graph &g,int &k,vector<int> &cmp){
    int n=g.size();
    Graph rg(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<g[i].size();j++) rg[g[i][j]].push_back(i);
    }
    vector<int> vs;
    cmp.assign(n,0);
    vector<bool> used(n, false);
    function<void(int)> dfs = [&g, &vs, &used, &dfs](int v) {
        used[v] = true;
        for (int i: g[v]) if (!used[i]) dfs(i);
        vs.push_back(v);
    };
  
  function<void(int,int)> rdfs = [&rg, &cmp, &used, &rdfs](int v, int k) {
    used[v] = true; cmp[v] = k;
    for (int i: rg[v]) if (!used[i]) rdfs(i, k);
  };
  for(int i=0;i<n;i++) if (!used[i]) dfs(i);
  fill(used.begin(),used.end(),false);
  reverse(vs.begin(),vs.end());
  k=0;
  for(int i: vs) if (!used[i]) rdfs(i, k++);
  return;
    
}


int main(){
    int n;
    cin>>n;
    vector<int> x(n),y(n);
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];
    }
    vector<pair<int,pair<int,int>>> pos;
    vector<int> posL;
    for(int i=0;i<n;i++){
        pos.push_back({x[i],{i,0}});
        pos.push_back({y[i],{i,1}});
        posL.push_back(x[i]);
        posL.push_back(y[i]);
    }
    sort(pos.begin(),pos.end());
    sort(posL.begin(),posL.end());
    vector<int> xpos(n);
    vector<int> ypos(n);
    for(int i=0;i<2*n;i++){
        if(pos[i].second.second){
            ypos[pos[i].second.first]=i;
        }
        else{
            xpos[pos[i].second.first]=i;
        }
    }

    int lb=0,ub=1e9+1;
    auto addEdge=[](Graph& g,int from,int x,int cnt){
        if(cnt<0) return;
        int v=x*20;
        int tox=x;
        for(int i=19;i>=0;i--){
            if((cnt-(1<<i))>=0){
                int to=tox*20+i;
                g[from].push_back(to);
                cnt-=(1<<i);
                tox+=(1<<i);
            }
        }
        return;
    };
    while(ub-lb>1){
        int mid=(ub+lb)/2;
        //build part
        Graph g(20*n*2);
        for(int i=0;i<2*n;i++){
            for(int j=1;j<20;j++){
                int v=i*20+j;
                int to0=i*20+j-1;
                int to1=min((i+(1<<(j-1))),2*n-1)*20+j-1;
                g[v].push_back(to0);
                g[v].push_back(to1);
            }
        }
        for(int i=0;i<n;i++){
            int from=20*ypos[i];
            int r=lower_bound(posL.begin(),posL.end(),x[i]+mid)-posL.begin();
            addEdge(g,from,xpos[i]+1,r-(xpos[i]+1));
            int l=upper_bound(posL.begin(),posL.end(),x[i]-mid)-posL.begin();
            addEdge(g,from,l,xpos[i]-l);
        }
        for(int i=0;i<n;i++){
            int from=20*xpos[i];
            int r=lower_bound(posL.begin(),posL.end(),y[i]+mid)-posL.begin();
            addEdge(g,from,ypos[i]+1,r-(ypos[i]+1));
            int l=upper_bound(posL.begin(),posL.end(),y[i]-mid)-posL.begin();
            addEdge(g,from,l,ypos[i]-l);
        }
        //check part
        int k;
        vector<int> cmp;
        SSC(g,k,cmp);
        
        bool isok=true;
        for(int i=0;i<n;i++){
            isok&=(cmp[20*xpos[i]]!=cmp[20*ypos[i]]);
        }
        if(isok) lb=mid;
        else ub=mid;
    }
    cout<<lb<<endl;
    return 0;
}

Submission Info

Judge Result