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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3641: 货车运输(树链剖分+持久化线段树)  

2014-07-03 14:52:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


首先如果在链上跑的话,可以随便分类讨论之后用持久化线段树搞掉,然后这是一个环套树,那么就树上的情况数链剖分+持久化线段树跑一跑,环上持久化线段树跑一跑,最后注意一下最小的那个点是一个二元环(比赛的时候被这个坑了就没A掉QAQ)。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <vector>

  •  

  • using namespace std ;

  •  

  • #define travel( x ) for ( edge *p = head[ x ] ; p ; p = p -> next )

  • #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 )

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

  •  

  • typedef long double ld ;

  •  

  • const int maxn = 101000 ;

  • const int maxm = maxn << 1 ;

  • const int maxu = 500000 ;

  •  

  • struct edge {

  •     int t , x ;

  •     ld l ;

  •     edge *next ;

  • } E[ maxm ] ;

  •  

  • edge *pe = E , *head[ maxn ] ;

  •  

  • inline void Init_edge(  ) {

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

  • }

  •  

  • inline void add( int s , int t , ld l , int x ) {

  •     pe -> t = t , pe -> l = l , pe -> x = x , pe -> next = head[ s ] ;

  •     head[ s ] = pe ++ ;

  • }

  •  

  • inline void addedge( int s , int t , ld l , int x ) {

  •     add( s , t , l , x ) , add( t , s , l , x ) ;

  • }

  •  

  • ld V[ maxn ] , W[ maxn ] ;

  • int n , m , q ;

  •  

  • bool del[ maxn ] , used[ maxn ] ;

  • int ve[ maxn ] , vn = 0 , sta[ maxn ] , tp = 0 , pos[ maxn ] ;

  • edge *edg[ maxn ] , *nxt[ maxn ] , *lst[ maxn ] ;

  •  

  • void dfs( int now , int fa ) {

  •     if ( vn ) return ;

  •     used[ now ] = true , sta[ pos[ now ] = ++ tp ] = now ;

  •     travel( now ) if ( p -> t != fa ) {

  •         if ( vn ) return ;

  •         if ( used[ p -> t ] ) {

  •             REP( i , pos[ p -> t ] , tp ) {

  •                 ve[ vn ] = sta[ i ] , lst[ vn ] = edg[ sta[ i ] ] , del[ sta[ i ] ] = true ;

  •                 vn ++ ;

  •             }

  •             lst[ 0 ] = p ;

  •             return ;

  •         } else {

  •             edg[ p -> t ] = p ;

  •             dfs( p -> t , now ) ;

  •         }

  •     }

  •     used[ now ] = false , -- tp ;

  • }

  •  

  • struct node {

  •     node *lc , *rc ;

  •     ld x , y ;

  •     node(  ) {

  •         x = y = 0 , lc = rc = NULL ;

  •     }

  • } sgt[ maxn * 20 ] ;

  •  

  • typedef node* np ;

  •  

  • np pt = sgt , null = sgt ;

  •  

  • inline void Init_sgt(  ) {

  •     ++ pt ;

  •     null -> lc = null -> rc = null , null -> x = null -> y = 0 ;

  • }

  •  

  • void add( int p , int l , int r , ld x , ld y , np &t , np u ) {

  •     if ( t == null ) t = pt ++ ;

  •     t -> x = u -> x + x , t -> y = u -> y + y ;

  •     if ( l == r ) return ;

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

  •     if ( p <= mid ) {

  •         t -> rc = u -> rc ;

  •         add( p , l , mid , x , y , t -> lc = null , u -> lc ) ;

  •     } else {

  •         t -> lc = u -> lc ;

  •         add( p , mid + 1 , r , x , y , t -> rc = null , u -> rc ) ;

  •     }

  • }

  •  

  • void query( int l , int r , int _l , int _r , ld &x , ld &y , np t ) {

  •     if ( l > r ) {

  •         x = y = 0 ; return ;

  •     }

  •     if ( l == _l && r == _r ) {

  •         x = t -> x , y = t -> y ; return ;

  •     }

  •     int mid = ( _l + _r ) >> 1 ;

  •     if ( r <= mid ) query( l , r , _l , mid , x , y , t -> lc ) ; else

  •         if ( l > mid ) query( l , r , mid + 1 , _r , x , y , t -> rc ) ; else {

  •             ld a , b ;

  •             query( l , mid , _l , mid , x , y , t -> lc ) ;

  •             query( mid + 1 , r , mid + 1 , _r , a , b , t -> rc ) ;

  •             x += a , y += b ;

  •         }

  • }

  •  

  • int h[ maxn ] , sz[ maxn ] , bel[ maxn ] , chd[ maxn ] , up[ maxn ][ 21 ] , col[ maxn ] , cc = 0 ;

  • edge *to[ maxn ] ;

  • vector < int > pth[ maxn ] ;

  •  

  • void getsz( int now , int fa ) {

  •     sz[ now ] = 1 , chd[ now ] = 0 , col[ now ] = cc ;

  •     travel( now ) if ( p -> t != fa && ! del[ p -> t ] ) {

  •         h[ p -> t ] = h[ now ] + 1 , to[ p -> t ] = p , up[ p -> t ][ 0 ] = now ;

  •         getsz( p -> t , now ) ;

  •         sz[ now ] += sz[ p -> t ] ;

  •         if ( ! chd[ now ] || sz[ p -> t ] > sz[ chd[ now ] ] ) chd[ now ] = p -> t ;

  •     }

  • }

  •  

  • np root[ maxn ] ;

  • int id[ maxn ] ;

  •  

  • void Link( int now , int fa , int u ) {

  •     id[ now ] = u , root[ now ] = null , pth[ u ].push_back( now ) ;

  •     if ( now != u ) {

  •         ld w = W[ to[ now ] -> x ] , v = V[ to[ now ] -> x ] , l = to[ now ] -> l ;

  •         ld x = ( w * l ) / v , y = w * l ;

  •         add( int( v + 0.1 ) , 1 , maxu , x , y , root[ now ] , root[ fa ] ) ;

  •     }

  •     if ( chd[ now ] ) {

  •         Link( chd[ now ] , now , u ) ;

  •         travel( now ) if ( p -> t != fa && p -> t != chd[ now ] && ! del[ p -> t ] ) {

  •             Link( p -> t , now , p -> t ) ;

  •         }

  •     }

  • }

  •  

  • inline void Init_lca(  ) {

  •     rep( i , 20 ) rep( j , n ) up[ j ][ i ] = up[ up[ j ][ i - 1 ] ][ i - 1 ] ;

  • }

  •  

  • inline int Lca( int u , int v ) {

  •     if ( h[ u ] < h[ v ] ) swap( u , v ) ;

  •     DOWN( i , 20 , 0 ) if ( h[ up[ u ][ i ] ] >= h[ v ] ) u = up[ u ][ i ] ;

  •     if ( v == u ) return v ;

  •     DOWN( i , 20 , 0 ) if ( up[ u ][ i ] != up[ v ][ i ] ) {

  •         u = up[ u ][ i ] , v = up[ v ][ i ] ;

  •     }

  •     return up[ u ][ 0 ] ;

  • }

  •  

  • inline ld query( int v , int he , int speed ) {

  •     ld x = 0 , y = 0 , a , b ;

  •     while ( h[ v ] > he ) {

  •         if ( h[ id[ v ] ] > he ) {

  •             query( 1 , speed , 1 , maxu , a , b , root[ v ] ) ; x += a ;

  •             query( speed + 1 , maxu , 1 , maxu , a , b , root[ v ] ) ; y += b ;

  •             v = id[ v ] ;

  •             if ( int( V[ to[ v ] -> x ] + 0.1 ) <= speed ) {

  •                 a = ( W[ to[ v ] -> x ] * to[ v ] -> l ) / V[ to[ v ] -> x ] ;

  •                 x += a ;

  •             } else {

  •                 b = W[ to[ v ] -> x ] * to[ v ] -> l ;

  •                 y += b ;

  •             }

  •             v = up[ v ][ 0 ] ;

  •         } else {

  •             int c = pth[ id[ v ] ][ he - h[ id[ v ] ] ] ;

  •             query( 1 , speed , 1 , maxu , a , b , root[ v ] ) ; x += a ;

  •             query( speed + 1 , maxu , 1 , maxu , a , b , root[ v ] ) ; y += b ;

  •             query( 1 , speed , 1 , maxu , a , b , root[ c ] ) ; x -= a ;

  •             query( speed + 1 , maxu , 1 , maxu , a , b , root[ c ] ) ; y -= b ;

  •             break ;

  •         }

  •     }

  •     return x + y / ld( speed ) ;

  • }

  •  

  • inline ld Query( int u , int v , int speed ) {

  •     int lca = Lca( u , v ) ;

  •     return query( u , h[ lca ] , speed ) + query( v , h[ lca ] , speed ) ;

  • }

  •  

  • np pre[ maxn ] ;

  •  

  • inline ld query_c( int l , int r , int speed ) {

  •     if ( l > r ) return 0 ;

  •     ld x = 0 , y = 0 , a , b ;

  •     query( 1 , speed , 1 , maxu , a , b , pre[ r ] ) ; x += a ;

  •     query( speed + 1 , maxu , 1 , maxu , a , b , pre[ r ] ) ; y += b ;

  •     query( 1 , speed , 1 , maxu , a , b , pre[ l ] ) ; x -= a ;

  •     query( speed + 1 , maxu , 1 , maxu , a , b , pre[ l ] ) ; y -= b ;

  •     return x + y / ld( speed ) ;

  • }

  •  

  • inline ld query_p( int p , int speed ) {

  •     ld x = 0 , y = 0 , a , b ;

  •     query( 1 , speed , 1 , maxu , a , b , pre[ p ] ) ; x += a ;

  •     query( speed + 1 , maxu , 1 , maxu , a , b , pre[ p ] ) ; y += b ;

  •     return x + y / ld( speed ) ;

  • }

  •  

  • inline ld cal( edge *p , int spd ) {

  •     return ( W[ p -> x ] * p -> l ) / min( ld( spd ) , V[ p -> x ] ) ;

  • }

  •  

  • int main(  ) {

  •     Init_edge(  ) , Init_sgt(  ) ;

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

  •     int s , t , x ; ld l ;

  •     double A , B ;

  •     rep( i , n ) {

  •         scanf( "%d%d%lf%d" , &s , &t , &A , &x ) ;

  •         l = A ;

  •         addedge( s , t , l , x ) ;

  •     }

  •     rep( i , m ) {

  •         scanf( "%lf%lf" , &A , &B ) ;

  •         V[ i ] = A , W[ i ] = B ;

  •     }

  •     if ( n == 2 ) {

  •         while ( q -- ) {

  •             scanf( "%d%d%d" , &s , &t , &x ) ;

  •             if ( s == t ) {

  •                 printf( "0.000000\n" ) ; continue ;

  •             }

  •             double ans = min( cal( head[ s ] , x ) , cal( head[ s ] -> next , x ) ) ;

  •             printf( "%.6f\n" , ans ) ;

  •         }

  •         return 0 ;

  •     }

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

  •     dfs( 1 , 0 ) ;

  •     Rep( i , vn ) pos[ ve[ i ] ] = i ;

  •     memset( h , 0 , sizeof( h ) ) , memset( up , 0 , sizeof( up ) ) , memset( col , 0 , sizeof( col ) ) ;

  •     Rep( i , vn ) travel( ve[ i ] ) if ( ! del[ p -> t ] ) {

  •         to[ p -> t ] = p , bel[ p -> t ] = ve[ i ] ;

  •         h[ p -> t ] = 1 , root[ p -> t ] = null , ++ cc ;

  •         getsz( p -> t , 0 ) ;

  •         Link( p -> t , 0 , p -> t ) ;

  •     }

  •     ld X , Y , a , b ;

  •     a = V[ lst[ 0 ] -> x ] , b = W[ lst[ 0 ] -> x ] ;

  •     X = ( b * lst[ 0 ] -> l ) / a , Y = b * lst[ 0 ] -> l ;

  •     add( int( a + 0.1 ) , 1 , maxu , X , Y , pre[ 0 ] = null , null ) ;

  •     REP( i , 1 , ( vn - 1 ) ) {

  •         a = W[ lst[ i ] -> x ] , b = V[ lst[ i ] -> x ] ;

  •         X = ( a * lst[ i ] -> l ) / b , Y = a * lst[ i ] -> l ;

  •         add( int( b + 0.1 ) , 1 , maxu , X , Y , pre[ i ] = null , pre[ i - 1 ] ) ;

  •     }

  •     Init_lca(  ) ;

  •     ld ans ;

  •     while ( q -- ) {

  •         scanf( "%d%d%d" , &s , &t , &x ) ;

  •         if ( col[ s ] == col[ t ] && ! del[ s ] ) {

  •             ans = Query( s , t , x ) ;

  •         } else {

  •             ans = 0 ;

  •             if ( ! del[ s ] ) {

  •                 ans += query( s , 1 , x ) ;

  •                 DOWN( i , 20 , 0 ) if ( h[ up[ s ][ i ] ] > 1 ) {

  •                     s = up[ s ][ i ] ;

  •                 }

  •                 if ( h[ s ] > 1 ) s = up[ s ][ 0 ] ;

  •                 ans += cal( to[ s ] , x ) ;

  •                 s = bel[ s ] ;

  •             }

  •             if ( ! del[ t ] ) {

  •                 ans += query( t , 1 , x ) ;

  •                 DOWN( i , 20 , 0 ) if ( h[ up[ t ][ i ] ] > 1 ) {

  •                     t = up[ t ][ i ] ;

  •                 }

  •                 if ( h[ t ] > 1 ) t = up[ t ][ 0 ] ;

  •                 ans += cal( to[ t ] , x ) ;

  •                 t = bel[ t ] ;

  •             }

  •             s = pos[ s ] , t = pos[ t ] ;

  •             if ( s > t ) swap( s , t ) ;

  •             ans += min( query_c( s , t , x ) , query_c( t , vn - 1 , x ) + query_p( s , x ) ) ;

  •         }

  •         printf( "%.6f\n" , double( ans ) ) ;

  •     }

  •     return 0 ;

  • }



  评论这张
 
阅读(24)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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