QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#157776#7103. Red Black Treeucup-team956#AC ✓1768ms34296kbC++204.2kb2023-09-02 15:50:122023-09-02 15:50:12

Judging History

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

  • [2023-09-02 15:50:12]
  • 评测
  • 测评结果:AC
  • 用时:1768ms
  • 内存:34296kb
  • [2023-09-02 15:50:12]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std ;
using ll = long long ; 

const int N = 1e6 + 5 ;
using pii = pair<int,int> ;

struct LCA {
    int n ; 
    vector<vector<int>> f ; 
    vector<ll> dep ;
    vector<int> L , R , dfn ; 
    LCA() {}
    LCA(const vector<ll>& ndep , const vector<int>& NL , const vector<int>& NR , const vector<int>& ndfn) { // base-0
        dfn = ndfn , L = NL , R = NR ; 
        n = dfn.size() , f = vector(__lg(n) + 1 , vector<int>(n)) ; 

        dep = vector(ndfn.size() , 0ll) ; 
        for (int i = 0 ; i < n ; ++ i) dep[i] = ndep[dfn[i]] ; 
        dep[0] = LLONG_MAX ; 

        for (int i = 0 ; i < n ; ++ i) f[0][i] = i ; 

        for (int k = 1 ; k <= __lg(n) ; ++ k)
            for (int i = 0 ; i + (1 << k) - 1 < n ; ++ i) {
                f[k][i] = dep[f[k - 1][i]] < dep[f[k - 1][i + (1 << (k - 1))]] ? f[k - 1][i] : f[k - 1][i + (1 << (k - 1))] ; 
            }
    }
    ll query(int u , int v) { // assert(l <= r)
        int l = min(L[u] , L[v]) , r = max(R[u] , R[v]) ; 
        int len = __lg(r - l + 1) ; 
        int res = dep[f[len][l]] < dep[f[len][r - (1 << len) + 1]] ? f[len][l] : f[len][r - (1 << len) + 1] ; 
        return dfn[res] ;
    }
};

int stk[N] , top ; 
void solve()
{
    int n , m , q ; 
    cin >> n >> m >> q ; 
    vector col(n + 1 , 0) ; 
    vector e(n + 1 , vector(0 , pii{})) ; 

    for (int i = 0 ; i < m ; ++ i) {
        int u ; 
        cin >> u ; 
        col[u] = 1 ; 
    }

    for (int i = 1 ; i < n ; ++ i) {
        int u , v , w ; 
        cin >> u >> v >> w ; 
        e[u].push_back({v , w}) , e[v].push_back({u , w}) ; 
    }

    vector ls(1 , 0) ;
    vector l(n + 1 , 0) , r(n + 1 , 0) ; 
    vector f(n + 1 , 0ll) ; 
    vector dep(n + 1 , 0ll) ;

    top = 0 ; 
    auto dfs = [&](auto &&dfs , int x , int fa) -> void {
        if (col[x] == 1) stk[++ top] = x ; 
        // cout << stk[0] << '\n' ; 
        assert(top) ;
        f[x] = dep[x] - dep[stk[top]] ; 

        ls.push_back(x) ;
        l[x] = ls.size() - 1 ; 
        for (auto [y , w] : e[x]) if (y != fa) {
            dep[y] = dep[x] + w ; 
            dfs(dfs , y , x) ;
            ls.push_back(x) ; 
        }
        r[x] = ls.size() - 1 ; 
        if (col[x] == 1) -- top ; 
    };
    dfs(dfs , 1 , 0) ;
    LCA lca(dep , l , r , ls);
    // for (int i : ls) cout << i << ' ' ; cout << '\n' ; 
    // for (int i = 1 ; i <= n ; ++ i) cout << f[i] << ' ' ; cout << '\n' ; 
    // for (int i = 1 ; i < ls.size() ; ++ i) {
    //     cout << l[i] << ' ' << r[i] << '\n' ; 
    //     cout << dep[i] << '\n' ; 
    //     cout << f[i] << '\n' ; 
    // }
    // for (int i = 1 ; i <= n ; ++ i) {
    //     for (int j = 1 ; j <= n ; ++ j) {
    //         cout << i << ' ' << j << ' ' << lca.query(i , j) << '\n' ; 
    //     }
    // }
    // cout << lca.query(3 , 1) << '\n' ; 
    // return ; 

    ll MAXV = *max_element(dep.begin() , dep.end()) ; 
    while (q--) {
        int m ; 
        cin >> m ; 
        vector v(m , 0) ; 
        for (auto &i : v) cin >> i ; 
        sort(v.begin() , v.end() , [&](int i , int j){
            return l[i] < l[j] ; 
        });
        auto check = [&](ll lim) -> bool {
            vector V(0 , 0) ; 
            ll max_dep = 0 ; 
            for (int i : v)
                if (f[i] > lim) V.push_back(i) , max_dep = max(max_dep , dep[i]) ; 
            if (V.empty()) return 1 ; 
            int u = V[0] , v = V.back() ; 
            // cout << u << ' ' << v << '\n' ; 
            int fa = lca.query(u , v) ;
            assert(1 <= fa && fa <= n) ; 
            return max_dep - dep[fa] <= lim ; 
        };

        ll L = 0 , R = MAXV + 3 ; 
        while (L < R) {
            ll mid = L + R >> 1 ; 
            if (check(mid)) R = mid ; 
            else L = mid + 1 ; 
        }
        cout << L << '\n' ; 
    }
}
int main()
{
    ios::sync_with_stdio(false) ; 
    cin.tie(0) , cout.tie(0) ; 

    int t ; cin >> t ; 
    while (t--) solve() ;
    return 0 ; 
}

/*
2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10

3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12

3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3
*/

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3884kb

input:

2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3

output:

4
5
3
8
0
0
0

result:

ok 7 lines

Test #2:

score: 0
Accepted
time: 1768ms
memory: 34296kb

input:

522
26 1 3
1
1 4 276455
18 6 49344056
18 25 58172365
19 9 12014251
2 1 15079181
17 1 50011746
8 9 2413085
23 24 23767115
22 2 26151339
26 21 50183935
17 14 16892041
9 26 53389093
1 20 62299200
24 18 56114328
11 2 50160143
6 26 14430542
16 7 32574577
3 16 59227555
3 15 8795685
4 12 5801074
5 20 57457...

output:

148616264
148616264
0
319801028
319801028
255904892
317070839
1265145897
1265145897
1072765445
667742619
455103436
285643094
285643094
285643094
317919339
0
785245841
691421476
605409472
479058444
371688030
303203698
493383271
919185207
910180170
919185207
121535083
181713164
181713164
181713164
181...

result:

ok 577632 lines

Extra Test:

score: 0
Extra Test Passed