QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#183866#7103. Red Black TreeBUET_POISSON#AC ✓1361ms77148kbC++235.9kb2023-09-19 22:35:492023-09-19 22:35:49

Judging History

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

  • [2023-09-19 22:35:49]
  • 评测
  • 测评结果:AC
  • 用时:1361ms
  • 内存:77148kb
  • [2023-09-19 22:35:49]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define pb push_back
#define mp make_pair
#define F first
#define S second


typedef pair<int, int> ii;
typedef pair<int, int> pii;


class STable {
    int n;
    pair<int,int> *cal;
    vector<ii> *SparseTable;
    ii (*comp)(ii,ii);
    void initialize() {
        int i,j;
        cal[1].second=1;
        for(i=1,j=1<<i; j<=n; i++,j=1<<i) {
            cal[j].first=1;
            cal[j].second=j;
        }
        for(i=2; i<=n; i++) {
            cal[i].first=cal[i].first+cal[i-1].first;
            if(cal[i].second==0) cal[i].second=cal[i-1].second;
        }
    }
public:
    STable() {

    }
    STable(vector<ii> &arr,ii (*f)(ii,ii)) {
        n=arr.size();
        comp=f;
        cal=new pair<int,int>[n+1];
        initialize();
        SparseTable=new vector<ii>[n];
        int i,j,m;
        for(i=0,j=0; i<n; i++) {
            SparseTable[i].push_back(arr[i]);
        }
        for(j=0,m=1<<j; m<n; j++,m=1<<j) {
            for(i=0; i+m<n; i++) {
                SparseTable[i].push_back(comp(SparseTable[i][j],SparseTable[i+m][SparseTable[i+m].size()-1]));
            }
        }
    }
    void inits(vector<ii> &arr,ii (*f)(ii,ii)) {
        n=arr.size();
        comp=f;
        cal=new pair<int,int>[n+1];
        initialize();
        SparseTable=new vector<ii>[n];
        int i,j,m;
        for(i=0,j=0; i<n; i++) {
            SparseTable[i].push_back(arr[i]);
        }
        for(j=0,m=1<<j; m<n; j++,m=1<<j) {
            for(i=0; i+m<n; i++) {
                SparseTable[i].push_back(comp(SparseTable[i][j],SparseTable[i+m][SparseTable[i+m].size()-1]));
            }
        }
    };
    ii query(int l,int r) {
        int difference=(r-l+1);
        return comp(SparseTable[l][cal[difference].first],SparseTable[r-cal[difference].second+1][cal[difference].first]);
    }
    ~STable() {
        int i;
        for(i=0; i<n; i++) {
            SparseTable[i].clear();
        }
        delete []SparseTable;
        delete []cal;
        comp=0;
    }
};
pii minimum(pii a,pii b) {
    return min(a,b);
}

//<<<<<<<<<<<<<<<<<<<<<<<Sparse Table Template Ended>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\\


vector<vector<ii>> adj;

class LCA {

public:


    vector<int> first,dis; // first position of a node
    vector< pii > euler; // .F = height; .S = node
    vector<int> vis;
    STable stableLca;

    LCA() {
        
        first.clear();
        dis.clear();
        euler.clear();
        vis.clear();
    }
    LCA(int n) {
        init(n);
    }
    void init(int n) {
        first.clear();
        dis.clear();
        euler.clear();
        vis.clear();
        vis.resize(n, 0);
        first.resize(n,0);
        dis.resize(n,0);
    }
    void createLCA() {
        dfs(1);
        stableLca.inits(euler,minimum);
    }
    void dfs(int u,int height = 0) {
        first[u] = euler.size();
        vis[u] = 1;
        dis[u] = height;
        euler.pb(mp(height,u));
        for(ii &y:adj[u]) {
            int v = y.F;
            if( !vis[v] ) {
                dfs(v,height+1);
                euler.pb(mp(height,u));
            }
        }
    }

    int findLca(int x,int y) {
        int lca = stableLca.query( min( first[x], first[y]), max( first[x],first[y]) ).S;
        return lca;
    }

    int findDistance(int u,int v) {
        int l = findLca(u,v);
        return dis[u] + dis[v] - 2*dis[l];
    }

    bool isAncestor(int u,int v) {
        return findLca(u,v) == u;
    }
};


vector<bool> isRed;
vector<ll> redDist;
vector<int> depth;
vector<ll> dist;

void dfs(int node, int par, ll rd) {

    if (isRed[node]) rd = 0;
    redDist[node] = rd;
    
    for (ii &v: adj[node]) {
        if (v.first == par) continue;
        dist[v.first] = dist[node] + v.second;
        depth[v.first] = depth[node] + 1;
        dfs(v.first, node, rd + (ll)v.second);
    }
}


void solve() {
    
    int n, m, q, x, u, v, w, k;
    cin >> n >> m >> q;

    isRed.assign(n+1, false);
    redDist.assign(n+1, 0);
    depth.assign(n+1, 0);
    dist.assign(n+1, 0);
    adj.clear();
    adj.resize(n+1);

    for (int i=0; i<m; i++) {
        cin >> x;
        isRed[x] = true;
    }

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

    LCA lca(n+1);

    lca.createLCA();
    dfs(1, 0, 0);


    while(q--) {
        cin >> k;
        vector<pair<ll, ll>> vs;
        for (int i=0; i<k; i++) {
            cin >> x;
            if (isRed[x]) continue;
            vs.push_back({redDist[x], x});
        }
        if (vs.size() < 2) {
            cout << "0\n";
            continue;
        }
        vs.push_back({0, 0});
        sort(vs.begin(), vs.end());
        reverse(vs.begin(), vs.end());
        ll ans = vs[1].first;
        ll mxDist = 0, cur_lca = vs[0].second, idx = vs[0].second;

        for (int i=2; i<vs.size(); i++) {
            int nLca = lca.findLca(vs[i-1].second, cur_lca);
            if (dist[vs[i-1].second] - dist[nLca] >= dist[idx] - dist[nLca]) {
                idx = vs[i-1].second;
            }
            mxDist = dist[idx] - dist[nLca];
            cur_lca = nLca;
            ans = min(ans, max(mxDist, vs[i].first));
        }

        cout << ans << endl;
    }

}
int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;
    while(t--) {
        solve();
    }
}
/*
2

3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3
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




*/

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1361ms
memory: 77148kb

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