QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#165874 | #7103. Red Black Tree | ucup-team1074 | AC ✓ | 881ms | 47116kb | C++20 | 2.7kb | 2023-09-05 22:29:07 | 2023-09-05 22:29:08 |
Judging History
answer
//
// Created by lv_shen on 2023/9/2.
//
#include <bits/stdc++.h>
#define endl "\n"
//#define int long long
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair<int, LL> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using i64 = long long;
LL n, m, q, fa[N][26], dep[N], depcost[N], cost[N];
int Log2[N];
vector<PII> g[N];
bool st[N];
int red[N];
void dfs (int x, int fath = 0, LL w = 0) {
if (st[x])
return;
st[x] = true;
dep[x] = dep[fath] + 1;
fa[x][0] = fath;
depcost[x] = depcost[fath] + w;
cost[x] = min (cost[x], cost[fath] + w);
//cost[x] = cost[fath] + w;
//if (red[x]) cost[x] = 0;
for (int i = 1; i <= 25; i++) {
fa[x][i] = fa[fa[x][i - 1]][i - 1];
}
for (auto [y, ww] : g[x]) {
dfs (y, x, ww);
}
}
int lca (int x, int y) {
if (dep[x] < dep[y])
swap (x, y);
while (dep[x] != dep[y])
x = fa[x][Log2[dep[x] - dep[y]]];
if (x == y) return x;
for (int j = 25; j >= 0; j--) {
if (fa[x][j] != fa[y][j]) {
x = fa[x][j], y = fa[y][j];
}
}
return fa[x][0];
}
bool cmp (int a, int b) {
return cost[a] < cost[b];
}
void solve () {
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) cost[i] = 1e18;
// for (int i = 0; i <= n; i++) {
// dep[i] = depcost[i] = 0;
// cost[i] = 1e18;
// red[i] = false;
// g[i].clear ();
// st[i] = false;
// }
for (int i = 0; i < m; i++) {
int r;
cin >> r;
red[r] = true;
cost[r] = 0;
}
for (int i = 1; i < n; i++) {
int u, v;
LL w;
cin >> u >> v >> w;
g[u].emplace_back (v, w);
g[v].emplace_back (u, w);
}
fa[1][0] = 0;
dfs (1);
// for (int i = 1; i <= n; i++) {
// cout << cost[i] << " " << depcost[i] << endl;
// }
while (q--) {
int k;
cin >> k;
vector<int> v;
for (int i = 0; i < k; i++) {
int t;
cin >> t;
v.push_back (t);
}
sort (v.begin (), v.end (), cmp);
i64 ans = cost[v[k - 1]];
int l = v[k - 1];
i64 maxdep = depcost[v[k - 1]];
for (int i = k - 1; i >= 0; i--) {
maxdep = std::max (maxdep, depcost[v[i]]);
l = lca (l, v[i]);
ans = std::min (ans, std::max ((i ? cost[v[i - 1]] : 0LL), maxdep - depcost[l]));
}
std::cout << ans << "\n";
}
for (int i = 0; i <= n; i++) {
dep[i] = depcost[i] = 0;
cost[i] = 1e18;
red[i] = false;
g[i].clear ();
st[i] = false;
}
}
signed main () {
std::ios::sync_with_stdio (false);
std::cin.tie (nullptr);
std::cout.tie (nullptr);
int t;
cin >> t;
for (int i = 2; i < N; ++i)
Log2[i] = Log2[i / 2] + 1;
// for (int i = 1; i <= 1000; i++) {
// cout << i << " " << Log2[i] << endl;
// }
while (t--) {
solve ();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 13680kb
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: 881ms
memory: 47116kb
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