| 记录编号 |
168194 |
评测结果 |
AAAAAAAAAAAAAAA |
| 题目名称 |
[USACO Open08]牛的邻居 |
最终得分 |
100 |
| 用户昵称 |
 ztx |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.225 s |
| 提交时间 |
2015-07-01 20:25:53 |
内存使用 |
13.26 MiB |
显示代码纯文本
/****************************************\
* Author : ztx
* Title : [cogs] 2006. [USACO Open08]牛的邻居
* ALG : 曼哈顿最小距离生成树
* CMT : 应该可以证明,若最小生成树上的边都不能连接两点,那么其它的边也不可能连接上这两个点
ms找好边了直接连....不用sort
UPD:出现过的错误
1> 只排了序但没有去重,会有错误
eg:
20 163
159 853
259 205
949 970
126 762
545 26
884 511
507 508
97 82
938 64
145 768
451 862
777 807
849 843
237 817
454 14
444 887
257 522
969 644
89 900
19 116
第18与20个点
2> infi设小了WA了一个点QAQ
* Time :
\****************************************/
#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
#define rep(i,l,r) for(i=(l);i< (r);i++)
#define rev(i,r,l) for(i=(r);i> (l);i--)
typedef long long ll ;
typedef double lf ;
typedef long double llf ;
typedef unsigned uint ;
typedef unsigned long long ull ;
#define Strlen 10000010LL
char Stream[Strlen] , *ptr = Stream ;
#define Getchar() (*ptr++)
//#define Getchar() getchar()
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
ret = NEG = 0 ; while (CH=Getchar() , CH<'!') ;
if (CH == '-') NEG = true , CH = Getchar() ;
while (ret = ret*10+CH-'0' , CH=Getchar() , CH>'!') ;
if (NEG) ret = -ret ;
}
template <typename TP>inline void readc(TP& ret) {
while (ret=Getchar() , ret<'!') ;
while (CH=Getchar() , CH>'!') ;
}
template <typename TP>inline void reads(TP *ret) {
ret[0]=0;while (CH=Getchar() , CH<'!') ;
while (ret[++ret[0]]=CH,CH=Getchar(),CH>'!') ;
ret[ret[0]+1] = 0 ;
}
#include <algorithm>
#define maxn 100010LL
#define infi 0X7F7F7F7FLL
#define lb (p&(-p))
struct P {
int x , y , id ;
inline void in() { read(x) , read(y) ; }
inline void print() { printf("%d %d\n",x,y) ; }
inline void exchange() { if (x != y) x ^= y , y ^= x , x ^= y ; }
bool operator < (const P&b) const { return x==b.x ? (y-x)<(b.y-b.x) : x<b.x ; }
} points[maxn] ;
int n , C , ans1 , ans2 ;
int pos[maxn] , *posb[maxn] , minv[maxn] , minp[maxn] , sz[maxn] , fa[maxn] = {0} ;
inline void Bit_insert(int p,int val,int id) {
for ( ; p > 0 ; p -= lb)
if (val < minv[p])
minv[p] = val , minp[p] = id ;
}
int Bit_n ;
inline int Bit_query(int p) {
int tmp = infi , ret = -1 ;
for ( ; p <= Bit_n ; p += lb)
if (minv[p] < tmp)
tmp = minv[p] , ret = minp[p] ;
return ret ;
}
inline bool cmp(const int*a,const int*b) { return *a < *b ; }
inline int abss(int x) { return x<0 ? -x : x ; }
inline int Dist(int i,int j) { return abss(points[i].x-points[j].x)+abss(points[i].y-points[j].y) ; }
inline int GetAnc(int u) { return fa[u] ? fa[u]=GetAnc(fa[u]) : u ; }
inline void Union(int u,int v) {
u = GetAnc(u) , v = GetAnc(v) ;
if (u == v) return ;
ans1 -- , fa[v] = u ;
if (sz[u]+=sz[v] , sz[u]>ans2) ans2 = sz[u] ;
}
int main() {
int i , j , dir ;
#define READ
#ifdef READ
freopen("nabor.in" ,"r",stdin ) ;
freopen("nabor.out","w",stdout) ;
#endif
fread(Stream,1,Strlen,stdin) ;
read(n) , read(C) ;
Rep (i,1,n)
points[i].in() , points[i].id = i , sz[i] = 1 ;
ans1 = n , ans2 = 1 ;
rep (dir,0,4) {
if (dir & 1)
Rep (i,1,n) points[i].exchange() ;
else if (dir)
Rep (i,1,n) points[i].x = -points[i].x ;
std::sort(points+1 , points+n+1) ;// x从小到大
Rep (i,1,n) pos[i] = points[i].y-points[i].x , posb[i] = &pos[i] ;
std::sort(posb+1 , posb+n+1 , cmp) ;// y-x 从小到大
Bit_n = 0 ;
posb[0] = pos ;
pos[0] = infi ;
Rep (i,1,n) // 离散化去重
if (*posb[i] != *posb[i-1]) *posb[i-1] = ++Bit_n ;
else *posb[i-1] = Bit_n ;
Rev (i,n,1) *posb[i] = *posb[i-1] ;
Rep (i,1,Bit_n) minv[i] = infi , minp[i] = -1 ;
Rev (i,n,1) {
j = Bit_query(pos[i]);
if (j!=-1 && Dist(i,j)<=C)
Union(points[i].id , points[j].id) ;
Bit_insert(pos[i] , points[i].x+points[i].y , i) ;
}
}
printf("%d %d\n", ans1 , ans2) ;
#ifdef READ
fclose(stdin) ; fclose(stdout) ;
#else
Getchar() ; Getchar() ;
#endif
return 0 ;
}