QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#157423 | #7103. Red Black Tree | ucup-team180# | AC ✓ | 1117ms | 37172kb | C++14 | 3.3kb | 2023-09-02 15:19:41 | 2023-09-02 15:19:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct sparse_table_lca{
vector<long long> D;
vector<vector<int>> ST;
int dmin(int u, int v){
if (D[u] < D[v]){
return u;
} else {
return v;
}
}
sparse_table_lca(int N, vector<int> A, vector<long long> D): D(D){
int M = A.size();
int LOG = 32 - __builtin_clz(M);
ST = vector<vector<int>>(LOG, vector<int>(M));
for (int i = 0; i < M; i++){
ST[0][i] = A[i];
}
for (int i = 0; i < LOG - 1; i++){
for (int j = 0; j < M - (1 << i); j++){
ST[i + 1][j] = dmin(ST[i][j], ST[i][j + (1 << i)]);
}
}
}
int query(int L, int R){
int d = 31 - __builtin_clz(R - L);
return dmin(ST[d][L], ST[d][R - (1 << d)]);
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (int i = 0; i < T; i++){
int n, m, q;
cin >> n >> m >> q;
vector<int> r(m);
for (int j = 0; j < m; j++){
cin >> r[j];
r[j]--;
}
vector<bool> red(n, false);
for (int j = 0; j < m; j++){
red[r[j]] = true;
}
vector<vector<pair<int, int>>> E(n);
for (int j = 0; j < n - 1; j++){
int u, v, w;
cin >> u >> v >> w;
u--;
v--;
E[u].push_back(make_pair(w, v));
E[v].push_back(make_pair(w, u));
}
vector<int> p(n, -1);
vector<vector<int>> c(n);
vector<long long> d(n, 0);
vector<long long> dp(n, 0);
queue<int> Q;
Q.push(0);
while (!Q.empty()){
int v = Q.front();
Q.pop();
for (pair<int, int> e : E[v]){
int w = e.second;
if (w != p[v]){
p[w] = v;
c[v].push_back(w);
d[w] = d[v] + e.first;
dp[w] = dp[v] + e.first;
if (red[w]){
dp[w] = 0;
}
Q.push(w);
}
}
}
vector<int> dv;
vector<int> in(n);
auto dfs = [&](auto dfs, int v) -> void {
in[v] = dv.size();
dv.push_back(v);
for (int w : c[v]){
dfs(dfs, w);
dv.push_back(v);
}
};
dfs(dfs, 0);
sparse_table_lca ST(n, dv, d);
auto lca = [&](int u, int v){
if (in[u] > in[v]){
swap(u, v);
}
return ST.query(in[u], in[v] + 1);
};
for (int j = 0; j < q; j++){
int k;
cin >> k;
vector<int> v(k);
for (int l = 0; l < k; l++){
cin >> v[l];
v[l]--;
}
sort(v.begin(), v.end(), [&](int x, int y){
return dp[x] < dp[y];
});
vector<long long> cdp(k);
for (int l = 0; l < k; l++){
cdp[l] = dp[v[l]];
}
vector<int> S(k);
S[k - 1] = v[k - 1];
for (int l = k - 2; l >= 0; l--){
S[l] = lca(v[l], S[l + 1]);
}
vector<long long> M(k);
M[k - 1] = d[v[k - 1]];
for (int l = k - 2; l >= 0; l--){
M[l] = max(d[v[l]], M[l + 1]);
}
long long tv = cdp[k - 1], fv = -1;
while (tv - fv > 1){
long long mid = (tv + fv) / 2;
int t = upper_bound(cdp.begin(), cdp.end(), mid) - cdp.begin();
if (M[t] - d[S[t]] <= mid){
tv = mid;
} else {
fv = mid;
}
}
cout << tv << '\n';
}
}
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3692kb
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: 1117ms
memory: 37172kb
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