QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#125567#6738. CoverSortingAC ✓826ms40656kbC++205.2kb2023-07-16 21:44:112023-07-16 21:44:13

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-16 21:44:13]
  • 评测
  • 测评结果:AC
  • 用时:826ms
  • 内存:40656kb
  • [2023-07-16 21:44:11]
  • 提交

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"