Submission #1120124
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;
#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------
class SCC {
public:
static const int MV = 1<<17;
vector<vector<int> > SC; int NV,GR[MV],rev[MV];
private:
vector<int> E[MV], RE[MV], NUM; int vis[MV];
public:
void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) { E[i].clear(); RE[i].clear();}}
void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; rev[cu]=ind;
FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
void scc() {
int c=0; SC.clear(); SC.resize(MV); NUM.clear();
ZERO(vis); for(int i=0;i<NV;i++) if(!vis[i]) dfs(i);
ZERO(vis); for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){
revdfs(NUM[i],c); c++;
}
}
};
int N;
int X[101010],Y[101010];
int id[101010][2];
int mi;
vector<pair<int,int>> E;
SCC sc;
void add(int c,int x,int y,int l=0,int r=1<<16,int k=1) { // x<=i<y
if(x>=y) return;
if(r<=x || y<=l) return;
if(x<=l && r<=y) {
sc.add_edge(c,k);
}
else {
add(c,x,y,l,(l+r)/2,k*2);
add(c,x,y,(l+r)/2,r,k*2+1);
}
}
int ok(int v) {
int i,j;
int A=1<<16, B=1<<15;
sc.init(1<<17);
v--;
for(i=2;i<1<<16;i++) {
sc.add_edge(i,i*2);
sc.add_edge(i,i*2+1);
}
FOR(i,N) {
sc.add_edge(A+id[i][0]+B,A+id[i][1]);
sc.add_edge(A+id[i][1]+B,A+id[i][0]);
int x=lower_bound(ALL(E),make_pair(X[i]-v,0))-E.begin();
int y=lower_bound(ALL(E),make_pair(X[i]+v+1,0))-E.begin();
add(A+id[i][0],x+B,id[i][0]+B);
add(A+id[i][0],id[i][0]+1+B,y+B);
x=lower_bound(ALL(E),make_pair(Y[i]-v,0))-E.begin();
y=lower_bound(ALL(E),make_pair(Y[i]+v+1,0))-E.begin();
add(A+id[i][1],x+B,id[i][1]+B);
add(A+id[i][1],id[i][1]+1+B,y+B);
}
sc.scc();
FOR(i,B) if(sc.GR[A+i]==sc.GR[A+i+B]) return 0;
return 1;
}
void solve() {
int i,j,k,l,r,x,y; string s;
cin>>N;
FOR(i,N) {
cin>>X[i]>>Y[i];
if(X[i]>Y[i]) swap(X[i],Y[i]);
E.push_back({X[i],i});
E.push_back({Y[i],i+(1<<14)});
}
sort(ALL(E));
FOR(i,N) {
id[i][0]=lower_bound(ALL(E),make_pair(X[i],i))-E.begin();
id[i][1]=lower_bound(ALL(E),make_pair(Y[i],i+(1<<14)))-E.begin();
}
int ret=0;
for(i=29;i>=0;i--) if(ok(ret+(1<<i))) ret+=1<<i;
cout<<ret<<endl;
}
int main(int argc,char** argv){
string s;int i;
if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
FOR(i,argc-1) s+=argv[i+1],s+='\n';
FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
solve(); return 0;
}
Submission Info
Submission Time |
|
Task |
F - Flags |
User |
kmjp |
Language |
C++14 (GCC 5.4.1) |
Score |
1200 |
Code Size |
3015 Byte |
Status |
AC |
Exec Time |
1102 ms |
Memory |
31096 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 |
114 ms |
18300 KB |
00_example_02.txt |
AC |
115 ms |
18300 KB |
00_example_03.txt |
AC |
114 ms |
18296 KB |
01.txt |
AC |
130 ms |
18552 KB |
02.txt |
AC |
122 ms |
18424 KB |
03.txt |
AC |
118 ms |
18296 KB |
04.txt |
AC |
118 ms |
18296 KB |
05.txt |
AC |
118 ms |
18296 KB |
06.txt |
AC |
714 ms |
28796 KB |
07.txt |
AC |
714 ms |
28920 KB |
08.txt |
AC |
707 ms |
28952 KB |
09.txt |
AC |
130 ms |
18552 KB |
10.txt |
AC |
119 ms |
18424 KB |
11.txt |
AC |
119 ms |
18296 KB |
12.txt |
AC |
116 ms |
18296 KB |
13.txt |
AC |
118 ms |
18292 KB |
14.txt |
AC |
688 ms |
26616 KB |
15.txt |
AC |
703 ms |
26632 KB |
16.txt |
AC |
704 ms |
26624 KB |
17.txt |
AC |
132 ms |
18552 KB |
18.txt |
AC |
122 ms |
18424 KB |
19.txt |
AC |
787 ms |
28408 KB |
20.txt |
AC |
776 ms |
28280 KB |
21.txt |
AC |
1009 ms |
28184 KB |
22.txt |
AC |
1102 ms |
28184 KB |
23.txt |
AC |
1025 ms |
31096 KB |
24.txt |
AC |
744 ms |
29976 KB |
25.txt |
AC |
729 ms |
29208 KB |
26.txt |
AC |
780 ms |
29816 KB |
27.txt |
AC |
121 ms |
18300 KB |