QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#165359#7103. Red Black TreeOnly_y#AC ✓870ms64740kbC++202.4kb2023-09-05 17:43:272023-09-05 17:43:28

Judging History

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

  • [2023-09-05 17:43:28]
  • 评测
  • 测评结果:AC
  • 用时:870ms
  • 内存:64740kb
  • [2023-09-05 17:43:27]
  • 提交

answer

#include <bits/stdc++.h>

#define int long long

void solve() {
  int n, m, q;
  std::cin >> n >> m >> q;
  std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
  std::vector<bool> red(n + 1, false);
  for (int i = 1, x; i <= m; ++i) { std::cin >> x; red[x] = true; }
  for (int i = 1, u, v, w; i <= n - 1; ++i) {
    std::cin >> u >> v >> w;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }
  std::vector<int> depth(n + 1), cost(n + 1), lg(n + 1), dis(n + 1);
  std::vector<std::array<int, 30>> Fa(n + 1);
  for (int i = 1; i <= n; ++i) lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
  auto dfs = [&] (auto self, int u, int fa) -> void {
    depth[u] = depth[fa] + 1, Fa[u][0] = fa;
    for (int i = 1; i <= lg[depth[u]]; ++i) Fa[u][i] = Fa[Fa[u][i - 1]][i - 1];
    for (auto x : adj[u]) {
      if (x.first == fa) continue;
      dis[x.first] = dis[u] + x.second;
      self(self, x.first, u);
    }
  };
  auto dfs1 = [&] (auto self, int u, int fa, int now) -> void {
    if (red[u]) now = std::max(now, dis[u]);
    cost[u] = dis[u] - now;
    for (auto x : adj[u]) {
      if (x.first == fa) continue;
      self(self, x.first, u, now);
    }
  };
  auto LCA = [&] (int x, int y) {
    if (depth[x] < depth[y]) std::swap(x, y);
    while (depth[x] > depth[y]) x = Fa[x][lg[depth[x] - depth[y]] - 1];
    if (x == y) return x;
    for (int k = lg[depth[x]] - 1; ~k; --k) {
      if (Fa[x][k] != Fa[y][k]) {
        x = Fa[x][k], y = Fa[y][k];
      }
    }
    return Fa[x][0];
  };
  dfs(dfs, 1, 0);
  dfs1(dfs1, 1, 0, 0);
  while (q --) {
    int k;
    std::cin >> k;
    std::vector<std::pair<int, int>> a(k + 1);
    for (int i = 1; i <= k; ++i) {
      std::cin >> a[i].second;
      a[i].first = cost[a[i].second];
    }
    if (k == 1) {
      std::cout << 0 << '\n';
      continue;
    }
    std::sort(a.begin() + 1, a.end());
    int ans = a.back().first;
    int lca = a.back().second;
    int mxdepth = dis[lca];
    for (int i = k; i >= 1; --i) {
      mxdepth = std::max(mxdepth, dis[a[i].second]);
      ans = std::min(ans, std::max(a[i - 1].first, mxdepth - dis[lca]));
      lca = LCA(lca, a[i - 1].second);
    }
    std::cout << ans << '\n';
  }
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int _(1);
  std::cin >> _;
  while (_ --) solve();
  return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3612kb

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: 870ms
memory: 64740kb

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