QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#187774 | #7103. Red Black Tree | UrgantTeam# | AC ✓ | 1061ms | 31996kb | C++23 | 3.7kb | 2023-09-24 22:10:23 | 2023-09-24 22:10:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct pt {
int lca;
ll w_pref, best_pref;
};
int const maxn = 1e5 + 5, logg = 17;
vector < pair < int, int > > g[maxn];
ll pref[maxn];
int tin[maxn], tout[maxn], cur, h[maxn], up[maxn][logg];
ll value[maxn];
int mark[maxn];
void dfs(int v, int p, ll best) {
tin[v] = cur++;
up[v][0] = p;
h[v] = h[p] + 1;
if (mark[v]) best = pref[v];
value[v] = best;
for (int j = 1; j < logg; j++) up[v][j] = up[up[v][j - 1]][j - 1];
for (auto [u, w] : g[v]) {
if (u == p) continue;
pref[u] = pref[v] + w;
dfs(u, v, best);
}
tout[v] = cur++;
}
int get_la(int v, int x) {
for (int i = 0; i < logg; i++) {
if ((x>>i)&1) v = up[v][i];
}
return v;
}
int get_lca(int v, int u) {
if (h[v] > h[u]) v = get_la(v, h[v] - h[u]);
else u = get_la(u, h[u] - h[v]);
if (u == v) return u;
for (int i = logg - 1; i >= 0; i--) {
if (up[v][i] != up[u][i]) v = up[v][i], u = up[u][i];
}
return up[v][0];
}
main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#endif // HOME
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, m, q, u, v, w;
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) g[i] = {}, mark[i] = 0;
for (int i = 1; i <= m; i++) {
cin >> u;
mark[u] = 1;
}
for (int i = 1; i < n; i++) {
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1, 0, 0);
for (int i = 1; i <= q; i++) {
int k;
cin >> k;
vector < int > node;
for (int j = 1; j <= k; j++) {
cin >> u;
node.push_back(u);
}
int mx = node[0];
for (auto key : node) {
if (pref[key] - value[key] > pref[mx] - value[mx]) mx = key;
}
ll ans = pref[mx] - value[mx];
vector < pt > all_lca;
for (auto key : node) {
all_lca.push_back({get_lca(mx, key), pref[key], value[key]});
}
ll cur = 0;
sort(all_lca.begin(), all_lca.end(), [](pt s, pt f) {
return h[s.lca] > h[f.lca];
});
int l = 0;
set < pair < ll, ll > > Q;
multiset < ll > mx_value;
vector < ll > suff(k + 1);
for (int i = k - 1; i >= 0; i--) {
suff[i] = max(suff[i + 1], all_lca[i].w_pref - all_lca[i].best_pref);
}
while (l < k) {
int r = l;
while (r < k && all_lca[l].lca == all_lca[r].lca) {
Q.insert({all_lca[r].best_pref, all_lca[r].w_pref});
mx_value.insert(all_lca[r].w_pref);
r++;
}
int now = all_lca[l].lca;
while (!Q.empty()) {
auto p = *Q.rbegin();
if (p.first >= pref[now]) {
cur = max(cur, p.second - p.first);
mx_value.erase(mx_value.find(p.second));
Q.erase(p);
} else break;
}
ll res = cur;
if (!Q.empty()) res = max(res, *mx_value.rbegin() - pref[now]);
res = max(res, suff[r]);
ans = min(ans, res);
l = r;
}
cout << ans << '\n';
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7936kb
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: 1061ms
memory: 31996kb
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