Submission #3767534
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;
}
}
const int LOGN=14;
int lb=0,ub=1e9+1;
auto addEdge=[](Graph& g,int from,int x,int cnt){
if(cnt<0) return;
int v=x*LOGN;
int tox=x;
for(int i=LOGN-1;i>=0;i--){
if((cnt-(1<<i))>=0){
int to=tox*LOGN+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(LOGN*n*2);
for(int i=0;i<2*n;i++){
for(int j=1;j<LOGN;j++){
int v=i*LOGN+j;
int to0=i*LOGN+j-1;
int to1=min((i+(1<<(j-1))),2*n-1)*LOGN+j-1;
g[v].push_back(to0);
g[v].push_back(to1);
}
}
for(int i=0;i<n;i++){
int from=LOGN*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=LOGN*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[LOGN*xpos[i]]!=cmp[LOGN*ypos[i]]);
}
if(isok) lb=mid;
else ub=mid;
}
cout<<lb<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Flags |
User |
nikutto |
Language |
C++14 (GCC 5.4.1) |
Score |
1200 |
Code Size |
3419 Byte |
Status |
AC |
Exec Time |
4561 ms |
Memory |
51012 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1200 / 1200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
All |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt |
Case Name |
Status |
Exec Time |
Memory |
00_example_01.txt |
AC |
2 ms |
256 KB |
00_example_02.txt |
AC |
2 ms |
256 KB |
00_example_03.txt |
AC |
5 ms |
384 KB |
01.txt |
AC |
101 ms |
2176 KB |
02.txt |
AC |
42 ms |
1056 KB |
03.txt |
AC |
12 ms |
512 KB |
04.txt |
AC |
14 ms |
576 KB |
05.txt |
AC |
16 ms |
600 KB |
06.txt |
AC |
3822 ms |
49564 KB |
07.txt |
AC |
3791 ms |
50620 KB |
08.txt |
AC |
3777 ms |
49564 KB |
09.txt |
AC |
106 ms |
2188 KB |
10.txt |
AC |
40 ms |
1060 KB |
11.txt |
AC |
12 ms |
512 KB |
12.txt |
AC |
14 ms |
576 KB |
13.txt |
AC |
15 ms |
640 KB |
14.txt |
AC |
3714 ms |
49188 KB |
15.txt |
AC |
3646 ms |
49048 KB |
16.txt |
AC |
3704 ms |
49048 KB |
17.txt |
AC |
102 ms |
2188 KB |
18.txt |
AC |
42 ms |
1056 KB |
19.txt |
AC |
3860 ms |
49016 KB |
20.txt |
AC |
4042 ms |
49580 KB |
21.txt |
AC |
4379 ms |
50948 KB |
22.txt |
AC |
4561 ms |
50980 KB |
23.txt |
AC |
4481 ms |
50816 KB |
24.txt |
AC |
3724 ms |
51012 KB |
25.txt |
AC |
3812 ms |
50956 KB |
26.txt |
AC |
3779 ms |
49276 KB |
27.txt |
AC |
2 ms |
256 KB |