QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#125567 | #6738. Cover | Sorting | AC ✓ | 826ms | 40656kb | C++20 | 5.2kb | 2023-07-16 21:44:11 | 2023-07-16 21:44:13 |
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()
const int MAXN = 1e5 + 7 ;
const int LOG = 18 ;
int n , m , k ;
vector < int > v[ MAXN ] ;
int lvl[ MAXN ] , LCA[ MAXN ][ LOG ] ;
int inc[ MAXN ] ;
int subtree[ MAXN ] ;
int heavy[ MAXN ] , root[ MAXN ] , pos[ MAXN ] ;
struct path {
int x , y , add ;
};
path hh[ 5 * MAXN ] ;
vector < int > at_lca[ MAXN ] ;
void init ( int x , int prv ) {
for ( int i = 1 ; i < LOG ; ++ i ) {
LCA[ x ][ i ] = LCA[ LCA[ x ][ i - 1 ] ][ i - 1 ] ;
}
subtree[ x ] = 1 ;
int tp = 0 ;
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
lvl[ y ] = lvl[ x ] + 1 ;
LCA[ y ][ 0 ] = x ;
inc[ y ] = tp ++ ;
init ( y , x ) ;
if ( subtree[ heavy[ x ] ] < subtree[ y ] ) {
heavy[ x ] = y ;
}
subtree[ x ] += subtree[ y ] ;
}
}
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 move_up ( int x , int cnt ) {
for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
if ( cnt >= ( 1 << i ) ) {
x = LCA[ x ][ i ] ;
cnt -= ( 1 << i ) ;
}
}
return x ;
}
ll tr[ MAXN ] ;
void update ( int x , ll add ) {
while ( x <= n ) {
tr[ x ] += add ;
x += ( x & -x ) ;
}
}
ll query ( int x ) {
ll ret = 0 ;
while ( x > 0 ) {
ret += tr[ x ] ;
x -= ( x & -x ) ;
}
return ret ;
}
ll get_sm ( int l , int r ) {
if ( l > r ) { return 0 ; }
return query ( r ) - query ( l - 1 ) ;
}
ll full[ MAXN ] ;
ll dp[ MAXN ][ 12 ] ;
ll sr[ ( 1 << 12 ) ] ;
ll aux[ ( 1 << 12 ) ] ;
ll get_path_sm ( ll down , ll up ) {
ll ret = full[ up ] ;
while ( root[ down ] != root[ up ] ) {
ret += get_sm ( pos[ root[ up ] ] , pos[ up ] - 1 ) ;
if ( LCA[ root[ up ] ][ 0 ] != down ) {
ret += dp[ LCA[ root[ up ] ][ 0 ] ][ inc[ root[ up ] ] ] ;
}
up = LCA[ root[ up ] ][ 0 ] ;
}
ret += get_sm ( pos[ down ] + 1 , pos[ up ] - 1 ) ;
return ret ;
}
void dfs ( int x , int prv ) {
int sz = 0 ;
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
++ sz ;
dfs ( y , x ) ;
}
for ( int i = 0 ; i < ( 1 << sz ) ; ++ i ) {
aux[ i ] = 0 , sr[ i ] = 0 ;
}
for ( auto id : at_lca[ x ] ) {
int mask = 0 ;
ll cand = hh[ id ].add ;
if ( hh[ id ].x != x ) {
mask += ( 1 << inc[ move_up ( hh[ id ].x , lvl[ hh[ id ].x ] - lvl[ x ] - 1 ) ] ) ;
cand += get_path_sm ( x , hh[ id ].x ) ;
}
if ( hh[ id ].y != x ) {
mask += ( 1 << inc[ move_up ( hh[ id ].y , lvl[ hh[ id ].y ] - lvl[ x ] - 1 ) ] ) ;
cand += get_path_sm ( x , hh[ id ].y ) ;
}
int lim = ( 1 << sz ) - 1 - mask ;
for ( int act = lim ; act > 0 ; act = ( act - 1 ) & lim ) {
aux[ act + mask ] = max ( aux[ act + mask ] , aux[ act ] + cand ) ;
}
aux[ mask ] = max ( aux[ mask ] , cand ) ;
}
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
int lim = ( 1 << sz ) - 1 - ( 1 << inc[ y ] ) ;
int mask = ( 1 << inc[ y ] ) ;
for ( int act = lim ; act > 0 ; act = ( act - 1 ) & lim ) {
aux[ act + mask ] = max ( aux[ act + mask ] , aux[ act ] + full[ y ] ) ;
}
aux[ mask ] = max ( aux[ mask ] , full[ y ] ) ;
}
full[ x ] = aux[ ( 1 << sz ) - 1 ] ;
for ( int i = 0 ; i < sz ; ++ i ) {
dp[ x ][ i ] = aux[ ( 1 << sz ) - 1 - ( 1 << i ) ] ;
}
update ( pos[ x ] , dp[ x ][ inc[ heavy[ x ] ] ] ) ;
}
void solve ( ) {
cin >> n >> m >> k ;
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 ) ;
for ( int i = 1 ; i <= m ; ++ i ) {
cin >> hh[ i ].x >> hh[ i ].y >> hh[ i ].add ;
at_lca[ get_lca ( hh[ i ].x , hh[ i ].y ) ].push_back ( i ) ;
}
int tp = 0 ;
for ( int i = 1 ; i <= n ; ++ i ) {
if ( heavy[ LCA[ i ][ 0 ] ] != i ) {
int x = i ;
while ( x > 0 ) {
root[ x ] = i ;
pos[ x ] = ++ tp ;
x = heavy[ x ] ;
}
}
}
dfs ( 1 , -1 ) ;
cout << full[ 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: 3ms
memory: 15276kb
input:
5 7 3 1 2 1 3 2 4 2 5 3 2 8 5 4 10 3 1 2 1 2 7 2 1 2 1 2 1 5 2 3
output:
19
result:
ok 1 number(s): "19"
Test #2:
score: 0
Accepted
time: 718ms
memory: 38072kb
input:
100000 500000 12 2 1 3 2 4 2 5 2 6 5 7 2 8 5 9 3 10 2 11 2 12 5 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 12 25 2 26 2 27 2 28 2 29 2 30 15 31 30 32 23 33 26 34 22 35 30 36 26 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 3 47 20 48 21 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 5...
output:
660925834533
result:
ok 1 number(s): "660925834533"
Test #3:
score: 0
Accepted
time: 768ms
memory: 39108kb
input:
100000 500000 12 2 1 3 2 4 1 5 4 6 2 7 5 8 2 9 7 10 8 11 3 12 11 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 22 24 8 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 26 34 27 35 23 36 13 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 3 47 14 48 8 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 58 4...
output:
664434138007
result:
ok 1 number(s): "664434138007"
Test #4:
score: 0
Accepted
time: 754ms
memory: 39260kb
input:
100000 500000 12 2 1 3 1 4 2 5 3 6 4 7 2 8 7 9 2 10 6 11 4 12 8 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 13 24 23 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 26 34 31 35 33 36 33 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 3 47 34 48 16 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 58 ...
output:
639691495391
result:
ok 1 number(s): "639691495391"
Test #5:
score: 0
Accepted
time: 756ms
memory: 39332kb
input:
100000 500000 12 2 1 3 1 4 2 5 1 6 5 7 4 8 2 9 1 10 4 11 8 12 7 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 14 22 14 23 21 24 20 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 2 34 23 35 31 36 7 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 3 47 3 48 29 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 58 3...
output:
662244733768
result:
ok 1 number(s): "662244733768"
Test #6:
score: 0
Accepted
time: 826ms
memory: 38124kb
input:
100000 500000 12 2 1 3 1 4 1 5 1 6 3 7 1 8 4 9 3 10 7 11 2 12 5 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 14 21 12 22 11 23 9 24 20 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 2 34 2 35 14 36 30 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 24 47 38 48 35 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 58...
output:
669458090009
result:
ok 1 number(s): "669458090009"
Test #7:
score: 0
Accepted
time: 378ms
memory: 40488kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 ...
output:
488921502446
result:
ok 1 number(s): "488921502446"
Test #8:
score: 0
Accepted
time: 325ms
memory: 39728kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 16 41 40 42 41 43 42 44 33 45 44 46 45 47 46 48 47 49 48 50 49 51 50 ...
output:
468137226275
result:
ok 1 number(s): "468137226275"
Test #9:
score: 0
Accepted
time: 332ms
memory: 39904kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 35 51 50 ...
output:
483733769728
result:
ok 1 number(s): "483733769728"
Test #10:
score: 0
Accepted
time: 332ms
memory: 40364kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 ...
output:
478945297872
result:
ok 1 number(s): "478945297872"
Test #11:
score: 0
Accepted
time: 371ms
memory: 40656kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 ...
output:
489443708266
result:
ok 1 number(s): "489443708266"
Test #12:
score: 0
Accepted
time: 575ms
memory: 23340kb
input:
10000 500000 12 2 1 3 2 4 1 5 1 6 2 7 5 8 2 9 8 10 6 11 8 12 4 13 11 14 1 15 6 16 5 17 10 18 17 19 12 20 8 21 16 22 1 23 5 24 21 25 23 26 3 27 18 28 6 29 8 30 15 31 1 32 30 33 17 34 23 35 5 36 24 37 33 38 25 39 34 40 1 41 24 42 11 43 6 44 18 45 28 46 25 47 32 48 40 49 29 50 43 51 33 52 9 53 2 54 20 ...
output:
560772428222
result:
ok 1 number(s): "560772428222"
Test #13:
score: 0
Accepted
time: 219ms
memory: 24744kb
input:
10000 500000 12 2 1 3 2 4 2 5 2 6 4 7 5 8 4 9 4 10 4 11 4 12 10 13 5 14 13 15 9 16 15 17 2 18 5 19 14 20 11 21 11 22 20 23 20 24 1 25 5 26 15 27 20 28 17 29 4 30 18 31 12 32 14 33 18 34 18 35 16 36 31 37 18 38 19 39 12 40 17 41 14 42 7 43 27 44 25 45 13 46 35 47 10 48 15 49 46 50 44 51 21 52 15 53 2...
output:
572767352204
result:
ok 1 number(s): "572767352204"
Test #14:
score: 0
Accepted
time: 340ms
memory: 21724kb
input:
10000 500000 12 2 1 3 1 4 2 5 2 6 2 7 4 8 7 9 7 10 2 11 9 12 3 13 1 14 7 15 9 16 8 17 2 18 13 19 12 20 2 21 16 22 8 23 13 24 8 25 20 26 25 27 14 28 4 29 28 30 4 31 12 32 13 33 24 34 1 35 21 36 5 37 16 38 28 39 35 40 28 41 13 42 20 43 19 44 16 45 40 46 28 47 3 48 5 49 14 50 2 51 4 52 47 53 47 54 15 5...
output:
585482767864
result:
ok 1 number(s): "585482767864"
Test #15:
score: 0
Accepted
time: 254ms
memory: 21568kb
input:
10000 500000 12 2 1 3 2 4 3 5 3 6 3 7 5 8 7 9 4 10 3 11 2 12 7 13 4 14 8 15 9 16 1 17 12 18 13 19 2 20 3 21 16 22 10 23 20 24 4 25 19 26 6 27 17 28 5 29 17 30 27 31 22 32 14 33 11 34 4 35 24 36 34 37 14 38 23 39 18 40 30 41 28 42 36 43 12 44 5 45 14 46 17 47 11 48 14 49 16 50 16 51 18 52 30 53 17 54...
output:
564574799774
result:
ok 1 number(s): "564574799774"
Test #16:
score: 0
Accepted
time: 262ms
memory: 22156kb
input:
10000 500000 12 2 1 3 1 4 2 5 2 6 4 7 6 8 5 9 8 10 7 11 7 12 5 13 1 14 5 15 11 16 9 17 3 18 4 19 10 20 8 21 2 22 11 23 18 24 10 25 8 26 16 27 22 28 11 29 20 30 12 31 4 32 19 33 27 34 6 35 1 36 24 37 18 38 30 39 32 40 10 41 9 42 15 43 34 44 27 45 34 46 7 47 34 48 39 49 32 50 13 51 11 52 38 53 17 54 5...
output:
575291114848
result:
ok 1 number(s): "575291114848"