QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408268#7103. Red Black Treeucup-team2010TL 0ms9676kbC++204.1kb2024-05-09 22:10:332024-05-09 22:10:35

Judging History

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

  • [2024-05-09 22:10:35]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:9676kb
  • [2024-05-09 22:10:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
#define pb push_back
using pll = pair<ll, ll>;
const int maxn = 1e5 + 5;
template<typename T>
struct BIT {
    int size;
    std::vector<T> c;
    BIT(int size = 0) {
        init(size);
    }
    void init(int size) {
        this->size = size;
        c.assign(size + 1, T());
    }
    T ask(int n) {
        T sum = 0;
        for (int i = n; i; i -= i & -i) {
            sum += c[i];
        }
        return sum;
    }
    void add(int pos, T x) {
        for (int i = pos; i <= size; i += i & -i) {
            c[i] += x;
        }
    }
    void modify(int l, int r, T x) {
        if (l > r)swap(l, r);
        add(l, x);
        add(r + 1, -x);
    }
    T getsum(T l, T r) {
        if (l > r)swap(l, r);
        return ask(r) - ask(l - 1);
    }
};
int fa[maxn][21];
int dfn[maxn], L[maxn], R[maxn], tot;
bool isRed[maxn];
int layer[maxn];
ll dep[maxn];
ll val[maxn];
struct edge {
    int v;
    ll w;
};
vector<edge>G[maxn];
void add(int u, int v, int w) {
    G[u].push_back({v, w});
    G[v].push_back({u, w});
}
int lg = 0;
void init(int n) {
    tot = 0;
    lg = __lg(n);
    function<void(int, int, ll, int)>dfs = [&](int u, int f, ll d, int redfa)->void{
        fa[u][0] = f;
        // cerr<<"u="<<u<<" fa[0]="<<fa[u][0]<<'\n';
        // dis[u][0]=d;
        dfn[++tot] = u;
        dep[u] = dep[f] + d;
        L[u] = tot;
        layer[u] = layer[f] + 1;
        if (isRed[u])redfa = u;
        val[u] = dep[u] - dep[redfa];
        for (auto [v, w] : G[u]) {
            if (v == f)continue;
            dfs(v, u, w, redfa);
        }
        R[u] = tot;
    };
    dfs(1, 0, 0, 0);
    for (int k = 1; k <= lg; k++) {
        for (int i = 1; i <= n; i++) {
            fa[i][k] = fa[fa[i][k - 1]][k - 1];
            // cerr<<"i="<<i<<" 1<<k="<<(1<<k)<<" fa="<<fa[i][k]<<'\n';
            // dis[i][k]=dis[i][k-1]+dis[fa[i][k-1]][k-1];
        }
    }
}
int calcFa(int u, ll d) {
    ll now = 0;
    for (int i = lg; i >= 0; i--) {
        int f = fa[u][i];
        if (f == 0)continue;
        ll dis = dep[u] - dep[f];
        if (now + dis <= d) {
            now += dis;
            u = f;
        }
    }
    return u;
}
int calcLCA(int u, int v) {
    if (layer[u] > layer[v])swap(u, v);
    for (int i = lg; i >= 0; i--) {
        if (layer[v] == layer[u])break;
        int f = fa[v][i];
        if (layer[f] >= layer[u]) {
            v = f;
        }
    }
    if (u == v)return u;
    for (int i = lg; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}
void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        G[i].clear();
    }
    fill(isRed, isRed + n + 1, false);
    for (int i = 1; i <= m; i++) {
        int r;
        cin >> r;
        isRed[r] = true;
    }
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    init(n);
    while (q--) {
        int k;
        cin >> k;
        vector<int>vec(k);
        for (int i = 0; i < k; i++) {
            cin >> vec[i];
        }
        ll l = -1, r = 1e14;
        auto check = [&](ll w) {
            std::vector<ll> now;
            for (auto q : vec) {
                if (val[q] > w)now.pb(q);
            }
            if (now.empty())return true;
            ll ffa = now[0];
            for (auto q : now) {
                ffa = calcLCA(ffa, q);
            }
            ll ans = 0;
            for (auto q : now) {
                ans = max(ans, dep[q] - dep[ffa]);
            }
            return (ans <= w);
        };
        while (l + 1 < r) {
            ll mid = (l + r) >> 1;
            if (check(mid))r = mid;
            else l = mid;
        }
        cout << r << "\n";
    }

}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);;
    int t = 1;
    cin >> t;
    while (t--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: