QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288637 | #7610. Bus Lines | Sorting | WA | 4ms | 79280kb | C++20 | 9.8kb | 2023-12-23 08:54:09 | 2023-12-23 08:54:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector<int> vi;
typedef vector < long long > vl ;
typedef unsigned int uint ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
const int MAXN = 4e5 + 7 ;
const int LOG = 20 ;
int n , m ;
vector < int > v[ MAXN ] ;
pii a[ MAXN ] ;
int subtree[ MAXN ] ;
vector < int > at_lca[ MAXN ] ;
vector < int > ending_at[ MAXN ] ;
int LCA[ MAXN ][ LOG ] , lvl[ MAXN ] ;
int st[ MAXN ] , en[ MAXN ] , tp ;
vector < int > ord ;
int hh_st[ MAXN ] , hh_en[ MAXN ] , hh_tp ;
void init ( int x , int prv ) {
st[ x ] = ++ tp ;
ord.push_back ( x ) ;
hh_st[ x ] = ++ hh_tp ;
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
LCA[ y ][ 0 ] = x ;
lvl[ y ] = lvl[ x ] + 1 ;
init ( y , x ) ;
ord.push_back ( x ) ;
++ hh_tp ;
}
en[ x ] = tp ;
hh_en[ x ] = hh_tp ;
}
ll down[ MAXN ] , up[ MAXN ] ; // down[ x ] - edge above x
ll child_sum[ MAXN ] ;
class Tree {
public :
ll tr[ MAXN ] ;
ll tot_add ;
void init ( ) {
tot_add = 0 ;
for ( int i = 0 ; i <= n ; ++ i ) { tr[ i ] = 0 ; }
}
void add_val ( int x , ll add ) {
if ( x == 0 ) { return ; }
while ( x <= n ) {
tr[ x ] += add ;
x += ( x & -x ) ;
}
}
void update ( int st , int en , ll add ) {
// tot_add += add ;
add_val ( st , add ) ;
add_val ( en + 1 , -add ) ;
}
ll query ( int x ) {
ll ret = tot_add ;
while ( x > 0 ) {
ret += tr[ x ] ;
x -= ( x & -x ) ;
}
return ret ;
}
};
Tree w ;
int mxpw[ MAXN ] ;
pii rmq[ MAXN ][ LOG ] ;
void init_rmq ( ) {
mxpw[ 1 ] = 0 ;
for ( int i = 1 ; i <= 2 * n ; ++ i ) {
mxpw[ i ] = mxpw[ i - 1 ] ;
if ( 2 * ( 1 << mxpw[ i ] ) < i ) { ++ mxpw[ i ] ; }
}
for ( int i = 1 ; i <= 2 * n ; ++ i ) {
int x = ord[ i - 1 ] ;
rmq[ i ][ 0 ] = { lvl[ x ] , x } ;
}
for ( int wh = 1 ; wh < LOG ; ++ wh ) {
for ( int i = 1 ; i + ( 1 << wh ) - 1 <= hh_tp ; ++ i ) {
rmq[ i ][ wh ] = min ( rmq[ i ][ wh - 1 ] , rmq[ i + ( 1 << ( wh - 1 ) ) ][ wh - 1 ] ) ;
}
}
}
int get_lca ( int x , int y ) {
/**
for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
if ( ( lvl[ x ] - ( 1 << i ) ) >= lvl[ y ] ) { x = LCA[ x ][ i ] ; }
if ( ( lvl[ y ] - ( 1 << i ) ) >= lvl[ x ] ) { y = LCA[ y ][ i ] ; }
}
for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
if ( LCA[ x ][ i ] != LCA[ y ][ i ] ) {
x = LCA[ x ][ i ] ;
y = LCA[ y ][ i ] ;
}
}
if ( x != y ) { x = LCA[ x ][ 0 ] ; }
return x ;
**/
int l = hh_st[ x ] , r = hh_st[ y ] ;
if ( l > r ) { swap ( l , r ) ; }
int len = r - l + 1 ;
int id = mxpw[ len ] ;
pii cand1 = rmq[ l ][ id ] , cand2 = rmq[ r - ( 1 << id ) + 1 ][ id ] ;
if ( cand1.fi < cand2.fi ) { return cand1.se ; }
return cand2.se ;
}
bool done ;
ll prec[ MAXN ] ;
ll path_val ( int x , int y ) {
int aux = get_lca ( x , y ) ;
// printf ( "path query %d %d -- %lld\n" , x , y , w.query ( 1 , 1 , n , st[ x ] ) + w.query ( 1 , 1 , n , st[ y ] ) - 2 * w.query ( 1 , 1 , n , st[ aux ] ) ) ;
if ( done == false ) {
return w.query ( st[ x ] ) + w.query ( st[ y ] ) - 2 * w.query ( st[ aux ] ) ;
}
return prec[ st[ x ] ] + prec[ st[ y ] ] - 2 * prec[ aux ] ;
}
ll hh[ MAXN ] ;
multiset < pii > s[ MAXN ] ;
void add_elem ( int wh , int x ) {
if ( s[ wh ].empty ( ) == true ) {
s[ wh ].insert ( { st[ x ] , x } ) ;
return ;
}
auto nxt = s[ wh ].lower_bound ( { st[ x ] , x } ) ;
auto prv = nxt ;
if ( nxt == s[ wh ].end ( ) ) { nxt = s[ wh ].begin ( ) ; }
if ( prv == s[ wh ].begin ( ) ) { prv = s[ wh ].end ( ) ; -- prv ; }
else { -- prv ; }
hh[ wh ] -= path_val ( prv->se , nxt->se ) ;
hh[ wh ] += path_val ( prv->se , x ) ;
hh[ wh ] += path_val ( x , nxt->se ) ;
s[ wh ].insert ( { st[ x ] , x } ) ;
}
void rem_elem ( int wh , int x ) {
if ( s[ wh ].size ( ) == 1 ) {
s[ wh ].clear ( ) ;
return ;
}
auto it = s[ wh ].find ( { st[ x ] , x } ) ;
auto nxt = it , prv = it ;
++ nxt ;
if ( nxt == s[ wh ].end ( ) ) { nxt = s[ wh ].begin ( ) ; }
if ( prv == s[ wh ].begin ( ) ) { prv = s[ wh ].end ( ) ; -- prv ; }
else { -- prv ; }
hh[ wh ] -= path_val ( prv->se , x ) ;
hh[ wh ] -= path_val ( x , nxt->se ) ;
hh[ wh ] += path_val ( prv->se , nxt->se ) ;
s[ wh ].erase ( it ) ;
}
void dfs_down ( int x , int prv ) {
int wh = 0 ;
subtree[ x ] = 1 ;
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
dfs_down ( y , x ) ;
subtree[ x ] += subtree[ y ] ;
child_sum[ x ] += down[ y ] ;
if ( s[ y ].size ( ) > s[ wh ].size ( ) ) { wh = y ; }
}
swap ( s[ wh ] , s[ x ] ) ;
hh[ x ] = hh[ wh ] ;
for ( auto y : v[ x ] ) {
if ( y == prv || y == wh ) { continue ; }
for ( auto [ pos , val ] : s[ y ] ) {
add_elem ( x , val ) ;
}
}
for ( auto id : at_lca[ x ] ) {
if ( a[ id ].fi != x ) { rem_elem ( x , a[ id ].fi ) ; }
if ( a[ id ].se != x ) { rem_elem ( x , a[ id ].se ) ; }
}
/**
printf ( "-- %d --> %d %lld %lld\n" , x , subtree[ x ] , hh[ x ] / 2 , child_sum[ x ] ) ;
for ( auto [ pos , val ] : s[ x ] ) {
printf ( "%d " , val ) ;
}
printf ( "\n" ) ;
**/
down[ x ] = subtree[ x ] ;
if ( s[ x ].empty ( ) == false ) {
add_elem ( x , x ) ;
down[ x ] += hh[ x ] / 2 + child_sum[ x ] ;
rem_elem ( x , x ) ;
}
else { down[ x ] += child_sum[ x ] ; }
// if ( x != 1 ) {
w.update ( st[ x ] , en[ x ] , child_sum[ x ] - down[ x ] ) ;
// }
for ( auto foo : ending_at[ x ] ) {
add_elem ( x , x ) ;
}
}
void dfs_out ( int x , int prv ) {
int wh = 0 ;
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
dfs_out ( y , x ) ;
if ( s[ wh ].size ( ) < s[ y ].size ( ) ) { wh = y ; }
}
swap ( s[ wh ] , s[ x ] ) ;
hh[ x ] = hh[ wh ] ;
for ( auto y : v[ x ] ) {
if ( y == prv || y == wh ) { continue ; }
for ( auto [ pos , val ] : s[ y ] ) {
add_elem ( x , val ) ;
}
}
for ( auto id : ending_at[ x ] ) {
int y = a[ id ].fi + a[ id ].se - x ;
add_elem ( x , y ) ;
}
for ( auto id : at_lca[ x ] ) {
if ( a[ id ].fi != x ) { rem_elem ( x , a[ id ].se ) ; }
if ( a[ id ].se != x ) { rem_elem ( x , a[ id ].fi ) ; }
}
/**
printf ( "AT VERTEX %d\n" , x ) ;
for ( auto [ pos , val ] : s[ x ] ) {
printf ( "%d " , val ) ;
}
printf ( "\n" ) ;
**/
up[ x ] = n - subtree[ x ] ;
if ( s[ x ].empty ( ) == false ) {
add_elem ( x , x ) ;
int tot_lca = get_lca ( (s[ x ].begin ( ))->se , (s[ x ].rbegin ( ))->se ) ;
up[ x ] += hh[ x ] / 2 + child_sum[ tot_lca ] - child_sum[ x ] ;
// printf ( "%lld %lld %lld up = %lld\n" , hh[ x ] , child_sum[ tot_lca ] , child_sum[ x ] , up[ x ] ) ;
rem_elem ( x , x ) ;
}
}
int mxup[ MAXN ] ;
void mrk ( int x , int prv ) {
int wh = 0 ;
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
mrk ( y , x ) ;
if ( s[ y ].size ( ) > s[ wh ].size ( ) ) { wh = y ; }
}
swap ( s[ x ] , s[ wh ] ) ;
for ( auto y : v[ x ] ) {
if ( y == prv || y == wh ) { continue ; }
for ( auto foo : s[ y ] ) {
s[ x ].insert ( foo ) ;
}
}
for ( auto id : ending_at[ x ] ) {
int aux = get_lca ( a[ id ].fi , a[ id ].se ) ;
s[ x ].insert ( { lvl[ aux ] , aux } ) ;
}
s[ x ].erase ( { lvl[ x ] , x } ) ;
if ( s[ x ].empty ( ) == true ) { mxup[ x ] = LCA[ x ][ 0 ] ; }
else { mxup[ x ] = (s[ x ].begin ( ))->se ; }
if ( mxup[ x ] == 0 ) { mxup[ x ] = x ; }
}
void dfs_up ( int x , int prv ) {
if ( mxup[ x ] != 1 ) {
up[ x ] += up[ mxup[ x ] ] ; // - ( subtree[ mxup[ x ] ] - subtree[ x ] ) ;
}
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
dfs_up ( y , x ) ;
}
}
void solve ( ) {
cin >> n ;
for ( int i = 1 , x , y ; i < n ; ++ i ) {
cin >> x >> y ;
v[ x ].push_back ( y ) ;
v[ y ].push_back ( x ) ;
}
init ( 1 , -1 ) ;
init_rmq ( ) ;
cin >> m ;
for ( int i = 1 ; i <= m ; ++ i ) {
cin >> a[ i ].fi >> a[ i ].se ;
int aux = get_lca ( a[ i ].fi , a[ i ].se ) ;
if ( a[ i ].fi != aux ) { ending_at[ a[ i ].fi ].push_back ( i ) ; }
if ( a[ i ].se != aux ) { ending_at[ a[ i ].se ].push_back ( i ) ; }
at_lca[ get_lca ( a[ i ].fi , a[ i ].se ) ].push_back ( i ) ;
}
w.init ( ) ;
dfs_down ( 1 , -1 ) ;
/**
for ( int i = 1 ; i <= n ; ++ i ) {
printf ( "down[ %d ] = %lld\n" , i , down[ i ] ) ;
}
**/
done = true ;
for ( int i = 1 ; i <= n ; ++ i ) {
prec[ i ] = w.query ( st[ i ] ) ;
s[ i ].clear ( ) ;
hh[ i ] = 0 ;
}
dfs_out ( 1 , -1 ) ;
/**
for ( int i = 1 ; i <= n ; ++ i ) {
printf ( "up[ %d ] = %lld\n" , i , up[ i ] ) ;
}
**/
for ( int i = 1 ; i <= n ; ++ i ) {
s[ i ].clear ( ) ;
hh[ i ] = 0 ;
}
mrk ( 1 , -1 ) ;
dfs_up ( 1 , -1 ) ;
for ( int i = 1 ; i <= n ; ++ i ) {
cout << up[ i ] + child_sum[ i ] << " " ;
}
cout << "\n" ;
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; // cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 79280kb
input:
6 1 2 5 4 6 5 3 1 1 5 3 6 1 2 3 6 4
output:
6 9 9 10 6 8
result:
wrong answer 1st lines differ - expected: '6 9 9 10 7 7', found: '6 9 9 10 6 8 '