注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-3237: [Ahoi2013]连通图(CDQ分治+并查集)  

2014-07-03 21:25:00|  分类: 分治,bzoj,oi,并 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=3237


对询问序列进行分治,然后利用并查集进行缩点(修改边即可),这样时间复杂度就可以达到了O(k log k)。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •   

  • using namespace std ;

  •   

  • #define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  • #define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

  • #define Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )

  •   

  • const int maxn = 101000 , maxm = 201000 , maxk = 101000 , maxd = 19 ;

  •   

  • int father[ maxn ] ;

  •   

  • inline void Init_us( int V ) {

  •         rep( i , V ) father[ i ] = 0 ;

  • }

  •   

  • inline int getfa( int now ) {

  •         int i = now ; for ( ; father[ i ] ; i = father[ i ] ) ;

  •         for ( int j = now , k ; father[ j ] ; k = father[ j ] , father[ j ] = i , j = k ) ;

  •         return i ;

  • }

  •   

  • inline void merge( int s , int t ) {

  •         int u = getfa( s ) , v = getfa( t ) ;

  •         if ( u != v ) father[ u ] = v ;

  • }

  •   

  • int edge[ maxm ][ 2 ] , en[ maxk ] , e[ maxk ][ 4 ][ 3 ] , n , m , k , num[ maxn ] , temp[ maxd ][ maxk ][ 4 ][ 2 ] , trans[ maxn ] ;

  • bool used[ maxm ] , ans[ maxk ] ;

  •   

  • inline int transform( int V , int l , int r ) {

  •         rep( i , V ) num[ i ] = 0 ;

  •         int cnt = 0 , now ;

  •         rep( i , V ) {

  •                 if ( ! num[ now = getfa( i ) ] ) num[ now ] = ++ cnt ;

  •                 trans[ i ] = num[ now ] ;

  •         }

  •         REP( i , l , r ) Rep( j , en[ i ] ) {

  •                 e[ i ][ j ][ 0 ] = trans[ e[ i ][ j ][ 0 ] ] , e[ i ][ j ][ 1 ] = trans[ e[ i ][ j ][ 1 ] ] ;

  •         }

  •         return cnt ;

  • }

  •   

  • inline void Save( int l , int r , int lev ) {

  •         REP( i , l , r ) Rep( j , en[ i ] ) {

  •                 temp[ lev ][ i ][ j ][ 0 ] = e[ i ][ j ][ 0 ] , temp[ lev ][ i ][ j ][ 1 ] = e[ i ][ j ][ 1 ] ;

  •         }

  • }

  •   

  • inline void Load( int l , int r , int lev ) {

  •         REP( i , l , r ) Rep( j , en[ i ] ) {

  •                 e[ i ][ j ][ 0 ] = temp[ lev ][ i ][ j ][ 0 ] , e[ i ][ j ][ 1 ] = temp[ lev ][ i ][ j ][ 1 ] ;

  •         }

  • }

  •   

  • int VI ;

  •   

  • inline void Init(  ) {

  •         scanf( "%d%d" , &n , &m ) ;

  •         rep( i , m ) scanf( "%d%d" , edge[ i ] , edge[ i ] + 1 ) ;

  •         scanf( "%d" , &k ) ;

  •         memset( used , false , sizeof( used ) ) ;

  •         rep( i , k ) {

  •                 scanf( "%d" , en + i ) ;

  •                 Rep( j , en[ i ] ) {

  •                         int x ; scanf( "%d" , &x ) ; used[ x ] = true ;

  •                         e[ i ][ j ][ 0 ] = edge[ x ][ 0 ] , e[ i ][ j ][ 1 ] = edge[ x ][ 1 ] , e[ i ][ j ][ 2 ] = x ;

  •                 }

  •         }

  •         Init_us( n ) ;

  •         rep( i , m ) if ( ! used[ i ] ) merge( edge[ i ][ 0 ] , edge[ i ][ 1 ] ) ;

  •         VI = transform( n , 1 , k ) ;

  • }

  •   

  • int flag[ maxm ] , tag = 0 ;

  •   

  • void solve( int V , int l , int r , int lev ) {

  •         if ( l == r ) {

  •                 ans[ l ] = V == 1 ; return ;

  •         }

  •         int mid = ( l + r ) >> 1 ;

  •         ++ tag ;

  •         REP( i , l , mid ) Rep( j , en[ i ] ) flag[ e[ i ][ j ][ 2 ] ] = tag ;

  •         Init_us( V ) ;

  •         REP( i , ( mid + 1 ) , r ) Rep( j , en[ i ] ) if ( flag[ e[ i ][ j ][ 2 ] ] < tag ) {

  •                 merge( e[ i ][ j ][ 0 ] , e[ i ][ j ][ 1 ] ) ;

  •         }

  •         Save( l , mid , lev ) ;

  •         int v = transform( V , l , mid ) ;

  •         solve( v , l , mid , lev + 1 ) ;

  •         Load( l , mid , lev ) ;

  •         ++ tag ;

  •         REP( i , ( mid + 1 ) , r ) Rep( j , en[ i ] ) flag[ e[ i ][ j ][ 2 ] ] = tag ;

  •         Init_us( V ) ;

  •         REP( i , l , mid ) Rep( j , en[ i ] ) if ( flag[ e[ i ][ j ][ 2 ] ] < tag ) {

  •                 merge( e[ i ][ j ][ 0 ] , e[ i ][ j ][ 1 ] ) ;

  •         }

  •         v = transform( V , mid + 1 , r ) ;

  •         solve( v , mid + 1 , r , lev + 1 ) ;

  • }

  •   

  • int main(  ) {

  •         Init(  ) ;

  •         memset( flag , 0 , sizeof( flag ) ) ;

  •         solve( VI , 1 , k , 0 ) ;

  •         rep( i , k ) printf( ans[ i ] ? "Connected\n" : "Disconnected\n" ) ;

  •         return 0 ;

  • }



  评论这张
 
阅读(39)| 评论(7)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017