QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288633 | #7610. Bus Lines | Sorting | TL | 1552ms | 73748kb | C++20 | 9.1kb | 2023-12-23 08:37:15 | 2023-12-23 08:37:15 |
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 = 2e5 + 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 ;
void init ( int x , int prv ) {
st[ x ] = ++ tp ;
for ( int i = 1 ; i < LOG ; ++ i ) {
LCA[ x ][ i ] = LCA[ LCA[ x ][ i - 1 ] ][ i - 1 ] ;
}
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
LCA[ y ][ 0 ] = x ;
lvl[ y ] = lvl[ x ] + 1 ;
init ( y , x ) ;
}
en[ x ] = tp ;
}
ll down[ MAXN ] , up[ MAXN ] ; // down[ x ] - edge above x
ll child_sum[ MAXN ] ;
class Tree {
public :
ll tr[ 4 * MAXN ] ;
void init ( int w , int l , int r ) {
tr[ w ] = 0 ;
if ( l == r ) { return ; }
int mid = ( l + r ) / 2 ;
init ( 2 * w , l , mid ) ;
init ( 2 * w + 1 , mid + 1 , r ) ;
}
void update ( int w , int l , int r , int st , int en , ll add ) {
if ( l > r || st > en ) { return ; }
if ( r < st || en < l ) { return ; }
if ( st <= l && r <= en ) {
tr[ w ] += add ;
return ;
}
int mid = ( l + r ) / 2 ;
update ( 2 * w , l , mid , st , en , add ) ;
update ( 2 * w + 1 , mid + 1 , r , st , en , add ) ;
}
ll query ( int w , int l , int r , int pos ) {
ll ret = 0 ;
while ( 1 ) {
ret += tr[ w ] ;
if ( l == r ) { return ret ; }
int mid = ( l + r ) / 2 ;
if ( pos <= mid ) {
w = 2 * w , r = mid ;
}
else {
w = 2 * w + 1 , l = mid + 1 ;
}
}
}
};
Tree w ;
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 ;
}
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 ] ) ) ;
return w.query ( 1 , 1 , n , st[ x ] ) + w.query ( 1 , 1 , n , st[ y ] ) - 2 * w.query ( 1 , 1 , n , st[ 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 ( 1 , 1 , n , 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 ) ;
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 ( 1 , 1 , n ) ;
dfs_down ( 1 , -1 ) ;
/**
for ( int i = 1 ; i <= n ; ++ i ) {
printf ( "down[ %d ] = %lld\n" , i , down[ i ] ) ;
}
**/
for ( int i = 1 ; i <= n ; ++ 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: 100
Accepted
time: 4ms
memory: 35580kb
input:
6 1 2 5 4 6 5 3 1 1 5 3 6 1 2 3 6 4
output:
6 9 9 10 7 7
result:
ok single line: '6 9 9 10 7 7 '
Test #2:
score: 0
Accepted
time: 4ms
memory: 35420kb
input:
2 1 2 1 1 2
output:
1 1
result:
ok single line: '1 1 '
Test #3:
score: 0
Accepted
time: 336ms
memory: 44668kb
input:
16384 9137 490 3442 7239 1621 6904 13769 10250 14672 12572 14906 9437 6163 12339 15244 12016 3022 8670 3211 9106 11966 14817 15798 15876 6423 7394 894 7695 13877 1983 16342 15158 13574 15932 15125 10722 6989 15683 10335 8801 12301 4246 6166 3893 9347 12073 7897 12195 6510 3101 4526 15385 7017 7001 4...
output:
34355 34048 34070 34152 33992 33977 34077 42219 34103 33976 34065 34170 34072 34061 34069 34177 34068 34129 33872 50478 34059 33921 34153 34049 34034 33820 34132 34116 34361 33728 50043 34138 33855 33873 34309 34319 34068 50753 34135 34256 34159 34034 34056 34361 34171 34316 34058 34125 34019 34182 ...
result:
ok single line: '34355 34048 34070 34152 33992 ... 34333 33814 33294 34266 34337 '
Test #4:
score: 0
Accepted
time: 1552ms
memory: 73748kb
input:
65536 44501 44259 59772 51161 51582 2027 2699 8610 5021 57211 60597 10270 29222 11423 38503 3833 52021 47503 47160 15296 61201 13465 20807 17239 7705 20234 32708 25663 7800 42265 29410 44963 32173 38920 49438 61282 25922 4342 40171 9819 12256 3995 41600 39383 57051 60932 44275 8351 8356 8295 3557 64...
output:
140178 136111 137025 136494 136304 137262 136598 135563 136530 135406 199677 137437 140282 136109 140127 136827 137235 136000 140738 139961 140081 142677 136544 201610 136181 136393 137013 137354 136855 135440 127050 136828 136781 137439 136518 185910 137170 136902 140686 136703 136847 137483 136337...
result:
ok single line: '140178 136111 137025 136494 13...63 136343 136858 137469 137325 '
Test #5:
score: -100
Time Limit Exceeded
input:
131071 28270 44685 69228 113487 10873 80967 30958 109340 53006 103488 49569 111875 65021 32861 83043 36671 73613 119374 22104 91373 31527 27737 19718 27803 90762 87148 4096 41649 79425 111516 111950 123500 94580 61416 30879 18640 71251 76344 61698 28557 104875 59268 130832 61334 110927 109064 114115...
output:
273557 262588 264936 265663 265875 266353 265834 265712 376149 272370 267699 267626 267023 265515 266009 265333 278296 265843 265760 268149 267395 265340 271825 358266 268835 264845 266112 265586 265886 266374 265323 265391 266080 265499 278600 267120 265190 266164 266010 265240 265690 265370 264312...