QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#183828#7103. Red Black TreeBUET_POISSON#TL 0ms3840kbC++205.9kb2023-09-19 21:36:102023-09-19 21:36:10

Judging History

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

  • [2023-09-19 21:36:10]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3840kb
  • [2023-09-19 21:36:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int 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;

template <class T>
class STable {
    int n;
    pair<int,int> *cal;
    vector<T> *SparseTable;
    T (*comp)(T,T);
    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<T> &arr,T (*f)(T,T)) {
        n=arr.size();
        comp=f;
        cal=new pair<int,int>[n+1];
        initialize();
        SparseTable=new vector<T>[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<T> &arr,T (*f)(T,T)) {
        n=arr.size();
        comp=f;
        cal=new pair<int,int>[n+1];
        initialize();
        SparseTable=new vector<T>[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]));
            }
        }
    };
    T 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>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\\


class LCA {

public:


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

    LCA() {
        adj.clear();
        first.clear();
        dis.clear();
        euler.clear();
        vis.clear();
    }
    LCA(int n) {
        init(n);
    }
    void init(int n) {
        adj.clear();
        first.clear();
        dis.clear();
        euler.clear();
        vis.clear();
        vis.resize(n, 0);
        adj.resize(n,vector<int>());
        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(int &v:adj[u]) {
            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<int> redDist;
vector<int> depth;
vector<int> dist;
vector<vector<ii>> adj;

void dfs(int node, int par, int 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 + v.second);
    }
}


void solve() {
    
    int n, m, q, x, u, v, w, k;
    scanf("%lld %lld %lld", &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++) {
        scanf("%lld", &x);
        isRed[x] = true;
    }
    
    for (int i=0; i<n-1; i++) {
        scanf("%lld %lld %lld", &u, &v, &w);
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    LCA lca(n+1);
    for (int i=1; i<=n; i++) {
        for (auto &v: adj[i]) {
            lca.adj[i].push_back(v.first);
        }
    }

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


    while(q--) {
        scanf("%lld", &k);
        vector<int> vs;
        for (int i=0; i<k; i++) {
            scanf("%lld", &x);
            if (isRed[x]) continue;
            vs.push_back(x);
        }
        int low = 0, high = 1e15;
        while(low < high) {
            int mid = (low + high) / 2;

            bool flag = true;
            vector<int> newV;
            for (int &x: vs) if (redDist[x] > mid) newV.push_back(x);
            if (newV.empty()) {
                high = mid;
                continue;
            }
            int curLca = newV[0];
            for (int &x: newV) curLca = lca.findLca(curLca, x);
            for (int &x: newV) if (dist[x] - dist[curLca] > mid) flag = false;
            if (flag) high = mid;
            else low = mid + 1;
        } 
        printf("%lld\n", low);
    }

}
signed main() {
    int t;
    scanf("%lld", &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




*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3840kb

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: -100
Time Limit Exceeded

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: