QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#523105 | #7103. Red Black Tree | mhw | AC ✓ | 770ms | 47128kb | C++20 | 3.0kb | 2024-08-17 20:21:01 | 2024-08-17 20:21:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#define endl '\n'
const int N = 2e5 + 5;
const int mod = 998244353;
int col[N], cost[N];
vector<pii> g[N];
int dep[N], fa[N][22], lg[N];
void dfs(int now, int fath)
{
fa[now][0] = fath;
dep[now] = dep[fath] + 1;
for (int i = 1; i <= lg[dep[now]]; i++)
fa[now][i] = fa[fa[now][i - 1]][i - 1];
for (auto [v, w] : g[now])
if (v != fath)
dfs(v, now);
}
void dfs1(int u, int f, int sum)
{
if (col[u]) sum = 0;
else cost[u] = sum;
for (auto [v, w]: g[u])
{
if (v == f) continue;
dfs1(v, u, sum + w);
}
}
int dis[N];
void dfs2(int u, int f, int sum)
{
dis[u] = sum;
for (auto [v, w]: g[u])
{
if (v == f) continue;
dfs2(v, u, sum + w);
}
}
int lca(int x, int y)
{
if (dep[x] < dep[y]) swap(x, y);
while (dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]] - 1];
if (x == y) return x;
for (int k = lg[dep[x]] - 1; k >= 0; k--)
if (fa[x][k] != fa[y][k])
x = fa[x][k], y = fa[y][k];
return fa[x][0];
}
struct node {
int i, w;
bool operator<(const node& p) {
return w > p.w;
}
};
void solve()
{
int n, m, q; cin >> n >> m >> q;
for (int i = 0; i <= n; i++)
{
col[i] = cost[i] = dep[i] = 0;
g[i].clear();
for (int j = 0; j <= 21; j++) fa[i][j] = 0;
}
for (int i = 1; i <= m; i++)
{
int x; cin >> x;
col[x] = 1;
}
for (int i = 1; i < n; i++)
{
int u, v, w; cin >> u >> v >> w;
g[u].push_back({v, w}), g[v].push_back({u, w});
}
dfs(1, 0);
dfs1(1, 0, 0);
dfs2(1, 0, 0);
while (q--)
{
int s; cin >> s;
vector<node> v;
for (int i = 1; i <= s; i++)
{
int x; cin >> x;
v.push_back({x, cost[x]});
}
if (s == 1)
{
cout << 0 << endl;
continue;
}
sort(v.begin(), v.end());
int l = v[0].i, maxx = dis[v[0].i], ans = v[1].w;
for (int i = 1; i < (int)v.size(); i++)
{
auto [x, w] = v[i];
l = lca(l, x);
maxx = max(maxx, dis[x]);
// cout << l << " " << maxx << endl;
if(i != (int)v.size() - 1)
ans = min(ans, max(maxx - dis[l], v[i + 1].w));
else ans = min(ans, maxx - dis[l]);
}
cout << ans << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
for (int i = 1; i < N; i++) lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
int T = 1; cin >> T;
while (T--) solve();
return 0;
}
/*
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
*/
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 10912kb
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: 770ms
memory: 47128kb
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