QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#286022 | #7607. The Doubling Game 2 | Sorting | TL | 1644ms | 327980kb | C++20 | 5.5kb | 2023-12-17 01:38:48 | 2023-12-17 01:38:48 |
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 ;
#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()
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const int MAXN = 3e5 + 7 ;
const int MOD = 1e9 + 7 ;
const int LOG = 21 ;
int n ;
vector < int > v[ MAXN ] ;
int subtree[ MAXN ] ;
int dp[ ( 1 << LOG ) ][ LOG ] , wtf[ ( 1 << LOG ) ][ LOG ] ; //
int root[ MAXN ][ LOG ] ; //
int complete[ MAXN ] ;
int mxpw[ MAXN ] ;
int f[ ( 1 << LOG ) ][ LOG ] ;
int bit_rv[ 2 * ( 1 << LOG ) ] ;
vector < int > bits[ ( 1 << LOG ) ] ;
bool cmp ( int x , int y ) {
return ( mxpw[ x ] < mxpw[ y ] ) ;
}
vector < int > children ;
static void dfs ( int x , int prv ) {
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
dfs ( y , x ) ;
}
children.clear ( ) ;
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
children.push_back ( y ) ;
}
sort ( children.begin ( ) , children.end ( ) , cmp ) ;
mxpw[ x ] = 0 ;
subtree[ x ] = 1 ;
for ( int i = 0 ; i < ( 1 << mxpw[ x ] ) ; ++ i ) {
for ( int j = 0 ; j < LOG ; ++ j ) {
f[ i ][ j ] = 0 ;
}
}
f[ 0 ][ LOG - 1 ] = 1 ;
for ( auto y : children ) {
subtree[ x ] += subtree[ y ] ;
int rem = mxpw[ x ] ;
mxpw[ x ] = max ( mxpw[ x ] , mxpw[ y ] ) ;
if ( mxpw[ x ] == mxpw[ y ] ) { ++ mxpw[ x ] ; }
// if ( mxpw[ x ] == mxpw[ y ] ) { ++ mxpw[ x ] ; }
while ( ( 1 << ( mxpw[ x ] - 1 ) ) >= subtree[ x ] ) { -- mxpw[ x ] ; }
// while ( mxpw[ x ] < LOG - 1 && ( 1 << mxpw[ x ] ) < subtree[ x ] ) { ++ mxpw[ x ] ; }
if ( rem < mxpw[ x ] ) {
int lo = ( 1 << rem ) ;
int hi = ( 1 << mxpw[ x ] ) - 1 ;
for ( int i = lo ; i <= hi ; ++ i ) {
for ( int j = 0 ; j < LOG ; ++ j ) {
f[ i ][ j ] = 0 ;
}
f[ i ][ LOG - 1 ] = 0 ;
}
}
rem = mxpw[ x ] ;
int mxseen = 0 ;
for ( int i = ( 1 << mxpw[ x ] ) - 1 ; i >= 0 ; -- i ) {
for ( int j = 0 ; j <= mxpw[ y ] ; ++ j ) {
if ( ( i & ( 1 << j ) ) == 0 ) {
if ( root[ y ][ j ] > 0 ) {
for ( int dig = j + 1 ; dig <= mxpw[ x ] ; ++ dig ) {
wtf[ ( i + ( 1 << j ) ) ][ dig ] = ( wtf[ ( i + ( 1 << j ) ) ][ dig ] + 1LL * f[ i ][ dig ] * root[ y ][ j ] ) % MOD ;
}
wtf[ ( i + ( 1 << j ) ) ][ LOG - 1 ] = ( wtf[ ( i + ( 1 << j ) ) ][ LOG - 1 ] + 1LL * f[ i ][ LOG - 1 ] * root[ y ][ j ] ) % MOD ;
}
wtf[ i ][ j ] = ( wtf[ i ][ j ] + 1LL * f[ i ][ LOG - 1 ] * dp[ y ][ j ] ) % MOD ;
}
wtf[ i ][ j ] = ( wtf[ i ][ j ] + 1LL * f[ i ][ j ] * complete[ y ] ) % MOD ;
}
wtf[ i ][ LOG - 1 ] = ( wtf[ i ][ LOG - 1 ] + 1LL * f[ i ][ LOG - 1 ] * complete[ y ] ) % MOD ;
}
for ( int i = ( 1 << mxpw[ x ] ) - 1 ; i >= 0 ; -- i ) {
for ( int dig = 0 ; dig <= mxpw[ x ] ; ++ dig ) {
f[ i ][ dig ] = wtf[ i ][ dig ] ;
wtf[ i ][ dig ] = 0 ;
}
f[ i ][ LOG - 1 ] = wtf[ i ][ LOG - 1 ] ;
wtf[ i ][ LOG - 1 ] = 0 ;
}
}
int act = 0 ;
for ( int mask = 0 ; mask < ( 1 << mxpw[ x ] ) ; ++ mask ) {
int lw = bit_rv[ ( ( ~mask ) & -( ~mask ) ) ] ; // smallest 0 bit id
// for ( int p1 = 0 ; p1 <= mxpw[ x ] ; ++ p1 ) {
for ( auto p1 : bits[ mask ] ) {
if ( p1 > mxpw[ x ] ) { continue ; }
if ( ( mask + ( 1 << lw ) ) == ( 1 << p1 ) - 1 ) {
dp[ x ][ lw ] = ( dp[ x ][ lw ] + f[ mask ][ p1 ] ) % MOD ;
act = max ( act , lw ) ;
}
if ( mask == ( 1 << p1 ) - 1 ) {
complete[ x ] = ( complete[ x ] + f[ mask ][ p1 ] ) % MOD ;
}
}
if ( ( ( mask + ( 1 << lw ) ) & ( mask + ( 1 << lw ) + 1 ) ) == 0 ) {
dp[ x ][ lw ] = ( dp[ x ][ lw ] + f[ mask ][ LOG - 1 ] ) % MOD ;
act = max ( act , lw ) ;
}
if ( ( mask & ( mask + 1 ) ) == 0 ) {
root[ x ][ lw ] = ( root[ x ][ lw ] + f[ mask ][ LOG - 1 ] ) % MOD ;
act = max ( act , lw ) ;
complete[ x ] = ( complete[ x ] + f[ mask ][ LOG - 1 ] ) % MOD ;
}
}
mxpw[ x ] = act ;
}
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 ) ;
}
for ( int i = 0 ; i < 2 * ( 1 << LOG ) ; ++ i ) {
bit_rv[ i ] = -1 ;
}
for ( int i = 0 ; i <= LOG ; ++ i ) {
bit_rv[ ( 1 << i ) ] = i ;
}
for ( int i = 0 ; i < ( 1 << LOG ) ; ++ i ) {
for ( int j = 0 ; j < LOG ; ++ j ) {
if ( ( i & ( 1 << j ) ) == 0 ) {
bits[ i ].push_back ( j ) ;
}
}
}
dfs ( 1 , -1 ) ;
cout << complete[ 1 ] << "\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: 336ms
memory: 233476kb
input:
5 1 2 1 3 1 4 4 5
output:
21
result:
ok single line: '21'
Test #2:
score: 0
Accepted
time: 329ms
memory: 233568kb
input:
1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 344ms
memory: 233504kb
input:
128 11 32 116 81 65 4 117 47 5 81 104 30 61 8 82 59 95 20 92 29 29 127 97 39 123 33 59 128 115 33 83 67 74 16 77 33 64 73 124 123 8 127 61 51 101 122 35 90 119 116 112 27 81 93 109 123 54 1 119 100 116 16 65 47 67 27 22 105 76 87 36 39 27 96 72 31 91 123 21 105 118 12 110 48 121 72 14 115 24 16 106 ...
output:
508800953
result:
ok single line: '508800953'
Test #4:
score: 0
Accepted
time: 377ms
memory: 233600kb
input:
256 53 177 57 242 74 90 107 104 209 169 132 70 152 142 71 168 143 99 91 130 202 140 49 165 209 193 209 137 159 188 247 48 49 21 20 208 155 185 120 231 83 87 37 84 143 18 106 8 114 79 191 158 208 256 133 252 215 92 199 108 166 168 39 217 85 69 204 139 100 75 111 6 230 198 79 130 26 155 155 38 55 81 1...
output:
999869740
result:
ok single line: '999869740'
Test #5:
score: 0
Accepted
time: 326ms
memory: 233716kb
input:
512 507 193 168 152 48 369 273 170 101 349 160 261 438 197 446 224 125 264 210 131 272 218 361 85 226 119 57 33 229 89 37 317 130 417 30 470 435 300 499 417 132 260 196 430 119 117 157 260 207 151 368 277 188 371 214 330 484 228 96 94 97 442 251 461 443 248 163 207 306 147 346 90 457 112 436 222 364...
output:
37387055
result:
ok single line: '37387055'
Test #6:
score: 0
Accepted
time: 347ms
memory: 233864kb
input:
1024 340 598 1 851 245 819 414 736 996 316 300 284 924 407 532 557 362 178 1006 469 397 373 742 77 112 37 406 892 703 666 496 825 1002 100 875 856 263 975 227 6 288 389 661 437 160 626 833 770 912 837 405 628 466 686 45 629 59 13 163 991 1017 422 208 247 344 376 709 956 570 272 996 954 518 454 267 3...
output:
689180079
result:
ok single line: '689180079'
Test #7:
score: 0
Accepted
time: 354ms
memory: 234040kb
input:
2048 2046 1942 589 1449 1593 1983 936 414 387 184 1962 1237 1986 635 573 1619 1598 1109 458 836 1123 1563 1502 519 1467 347 1815 864 980 405 709 433 1682 211 1967 1915 1089 1902 564 211 128 1004 1568 315 293 494 1552 1772 1641 1157 431 1899 1334 1623 161 1870 885 1330 1863 502 1761 1643 692 1759 118...
output:
275839338
result:
ok single line: '275839338'
Test #8:
score: 0
Accepted
time: 368ms
memory: 234676kb
input:
4096 2546 3568 3084 3426 1262 2128 1773 1455 425 3750 3444 3265 3099 464 3479 3651 639 1727 2486 2768 1165 1905 1847 2626 1335 3938 2550 1594 1520 1758 3771 2227 3486 60 381 383 1268 2829 1884 3468 3195 2892 983 31 584 2599 2811 1876 1875 3310 3184 2941 2893 202 1305 1926 1019 1639 3529 1998 2129 12...
output:
99235843
result:
ok single line: '99235843'
Test #9:
score: 0
Accepted
time: 380ms
memory: 235904kb
input:
8192 5663 2164 3712 1600 336 2388 1971 4169 1579 7319 496 8080 5305 982 5508 5777 5324 6680 4636 6745 7295 6086 6948 388 5239 811 1875 7271 5755 2864 2933 795 6448 6716 3016 302 2474 2937 6355 5936 4973 4064 2920 2318 6254 4090 665 2500 961 8180 5416 6371 4958 5430 7905 5013 4373 3068 6557 3867 3056...
output:
79832799
result:
ok single line: '79832799'
Test #10:
score: 0
Accepted
time: 400ms
memory: 238140kb
input:
16384 4535 8823 5344 1240 5793 15361 8423 14130 14595 11420 12195 1332 9712 4829 9533 14608 1328 14962 13846 1173 12823 5702 3518 9298 3235 13113 14312 3915 3439 9003 4667 5401 3819 2395 13827 981 3557 11804 7369 11344 15524 1435 4706 15539 12838 2109 4986 5367 2766 4313 6802 12338 12059 3998 6327 5...
output:
732760598
result:
ok single line: '732760598'
Test #11:
score: 0
Accepted
time: 485ms
memory: 244928kb
input:
32768 18706 23242 17650 5918 17278 24553 13070 18006 22702 10359 7113 13886 25578 16957 28955 27352 7353 6627 24042 21572 4744 30083 29267 16077 19328 1154 32271 23711 22390 3651 19272 7150 19081 13949 22123 4853 17958 18148 27675 28239 29486 26616 14292 23782 12790 18303 25184 9656 2671 13229 21875...
output:
383548244
result:
ok single line: '383548244'
Test #12:
score: 0
Accepted
time: 586ms
memory: 255824kb
input:
65536 58488 63309 5892 23044 42057 26219 45788 13164 16585 3001 4262 20408 60289 43446 44684 60172 60763 38228 56279 19103 45476 53988 42692 16285 17169 4001 23321 935 41892 8086 46236 15394 679 21542 26763 36111 47813 62044 22621 35997 6381 14778 17034 21699 54381 53287 35694 34830 14902 30504 5158...
output:
440039161
result:
ok single line: '440039161'
Test #13:
score: 0
Accepted
time: 360ms
memory: 233636kb
input:
2 2 1
output:
3
result:
ok single line: '3'
Test #14:
score: 0
Accepted
time: 939ms
memory: 280432kb
input:
131072 51230 116074 14356 18985 97302 87862 20350 65669 81694 54472 94257 44656 77121 118912 81235 115171 106881 104061 82683 25663 68305 12450 29336 62646 32572 74421 102407 112028 122054 79222 70569 123539 8651 78501 204 34510 69520 18129 55082 68106 51505 114323 100795 60383 61023 59864 57018 337...
output:
776456918
result:
ok single line: '776456918'
Test #15:
score: 0
Accepted
time: 1644ms
memory: 327980kb
input:
262144 131863 89153 74747 38646 187112 232634 203855 116743 1197 3109 104299 20430 195824 110378 144817 150658 187558 66008 261366 71448 227156 246386 4149 219771 47465 87425 185952 150310 20653 103389 4917 221350 124004 104544 162181 144076 79557 176106 88679 240655 234082 52601 205629 150797 20194...
output:
777533279
result:
ok single line: '777533279'
Test #16:
score: -100
Time Limit Exceeded
input:
300000 200042 33358 146127 282853 18162 208274 88763 197176 219535 47504 18973 156413 135038 231317 236314 79984 54777 75970 263068 185590 178314 16697 46633 171708 244101 108105 262612 237866 278911 257361 223742 114478 189208 195065 226678 182830 43889 137857 43488 17945 129846 57509 272492 132190...