QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#125564 | #6738. Cover | Sorting | WA | 725ms | 38920kb | C++20 | 5.1kb | 2023-07-16 21:34:32 | 2023-07-16 21:34:33 |
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 ) ;
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 ] ) ;
}
}
full[ x ] = aux[ ( 1 << sz ) - 1 ] ;
for ( int i = 0 ; i < sz ; ++ i ) {
dp[ x ][ i ] = aux[ ( 1 << sz ) - 1 - ( 1 << i ) ] ;
}
if ( prv != -1 && heavy[ prv ] == x ) {
update ( pos[ prv ] , 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: 12812kb
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: -100
Wrong Answer
time: 725ms
memory: 38920kb
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:
661938216238
result:
wrong answer 1st numbers differ - expected: '660925834533', found: '661938216238'