QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#168766#7103. Red Black TreeFu_suAC ✓1440ms47432kbC++175.0kb2023-09-08 21:23:292023-09-08 21:23:30

Judging History

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

  • [2023-09-08 21:23:30]
  • 评测
  • 测评结果:AC
  • 用时:1440ms
  • 内存:47432kb
  • [2023-09-08 21:23:29]
  • 提交

answer

#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>

std::vector<std::vector<std::pair<int, long long>>> E;
std::vector<char> vis;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int T;
  E.resize(1e5 + 5);
  vis.resize(1e5 + 5);
  for (std::cin >> T; T; --T) {
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<int> col(n + 1);
    for (int r, i = 1; i <= m; ++i) {
      std::cin >> r; col[r] = 1;
    }
    std::vector<std::vector<std::pair<int, int>>> e(n + 1);
    for (int i = 1, u, v, w; i < n; ++i) {
      std::cin >> u >> v >> w;
      e[u].push_back({v, w});
      e[v].push_back({u, w});
    }
    int vistime = 0;
    std::vector<int> anc(n + 1), stk, dfn(n + 1), euler, lastpos(n + 1), height(n + 1);
    std::vector<long long> sum(n + 1), ans(n + 1);
    auto dfs = [&](auto &&self, const int u) -> void {
      if (col[u] == 1) stk.push_back(u);
      dfn[u] = ++vistime;
      anc[u] = stk.back();
      ans[u] = sum[u] - sum[anc[u]];
      euler.push_back(u);
      lastpos[u] = euler.size() - 1;
      for (auto [v, w] : e[u]) if (anc[v] == 0) {
        height[v] = height[u] + 1;
        sum[v] = sum[u] + w;
        self(self, v);
        euler.push_back(u);
        lastpos[u] = euler.size() - 1;
      }
      if (col[u] == 1) stk.pop_back();
    };
    dfs(dfs, 1);
    auto minNode = [&](const int u, const int v) {
      if (height[u] < height[v]) return u;
      else return v;
    };
    std::vector ST(18, std::vector<int>(2 * (n + 3)));
    for (int i = 0; i < euler.size(); ++i) ST[0][i] = euler[i];
    for (int i = 0; i < 17; ++i) {
      for (int l = 0; l < euler.size(); ++l) {
        int r = l + (1 << (i + 1)) - 1;
        if (r >= euler.size()) break;
        int mid = l + (1 << (i));
        ST[i + 1][l] = minNode(ST[i][l], ST[i][mid]);
      }
    }
    auto LCA = [&](int u, int v) {
      int x = lastpos[u], y = lastpos[v];
      if (x > y) std::swap(x, y);
      int len = y - x + 1;
      return minNode(ST[log2(len)][x], ST[log2(len)][y - (1 << signed(log2(len))) + 1]);
    };
    auto dist = [&](int u, int v) {
      if (height[u] < height[v]) std::swap(u, v);
      return sum[u] - sum[v];
    };
    auto build_virtual_tree = [&](std::vector<int> &h, auto &e) {
      std::vector<int> a;
      std::sort(h.begin(), h.end(), [&](int a, int b) { return dfn[a] < dfn[b]; });
      for (int i = 0; i < h.size(); ++i) {
        a.push_back(h[i]);
        if (i + 1 != h.size()) {
          a.push_back(LCA(h[i], h[i + 1]));
        }
      }
      std::sort(a.begin(), a.end(), [&](int a, int b) { return dfn[a] < dfn[b]; });
      a.erase(std::unique(a.begin(), a.end()), a.end());
      std::vector<int> res;
      for (int i = 0; i < a.size() - 1; ++i) {
        int lc = LCA(a[i], a[i + 1]);
        e[lc].push_back({a[i + 1], dist(a[i + 1], lc)});
        e[a[i + 1]].push_back({lc, dist(a[i + 1], lc)});
        res.push_back(lc);
        res.push_back({a[i + 1]});
      }
      std::sort(res.begin(), res.end());
      res.erase(std::unique(res.begin(), res.end()), res.end());
      return res;
    };
    std::vector<int> iskey(n + 1);
    for (int k, x; q; --q) {
      std::vector<int> h;
      std::multiset<long long> s;
      long long res = 0;
      for (std::cin >> k; k; --k) {
        std::cin >> x;
        h.push_back(x);
        iskey[x] = 1;
        res = std::max(res, ans[x]);
        
      }
      int ances = 0;
      long long maxdep = 0;
      std::vector<int> keyNodes;
      for (auto u : h) if (ans[u] == res) {
        maxdep = sum[u];
        keyNodes.push_back(u);
        if (ances == 0) ances = anc[u];
        else if (anc[u] != ances) ances = -1;
      }
      if (ances == -1) {
        for (auto u : h) iskey[u] = 0;
        std::cout << res << '\n';
        continue;
      }
      long long resmax = 0;
      for (auto u : h) if (anc[u] == ances) {
        s.insert(ans[u]);
      } else {
        resmax = std::max(resmax, ans[u]);
      }
      k = h.size();
      for (int i = 0; i < k; ++i) h.push_back(anc[h[i]]);
      auto nodes = build_virtual_tree(h, E);
      int lca = keyNodes[0];
      for (int i = 1; i < keyNodes.size(); ++i) lca = LCA(keyNodes[i], lca);
      auto dfs2 = [&](auto &&self, int u) -> void {
        vis[u] = 1;
        if (iskey[u] && anc[u] == ances) s.erase(s.find(ans[u]));
        for (auto [v, w] : E[u]) if (height[v] > height[u] && vis[v] == 0 && col[v] == 0) {
          self(self, v);
        }
      };
      while (lca != ances) {
        dfs2(dfs2, lca);
        res = std::min(res, std::max({maxdep - sum[lca], (s.size() ? *s.rbegin() : 0ll), resmax}));
        for (auto [v, w] : E[lca]) if (height[v] < height[lca]) {
          lca = v; break;
        }
      }
      for (auto u : nodes) E[u].clear();
      std::cout << res << '\n';
      for (auto u : nodes) iskey[u] = vis[u] = 0;
    }
  }
}


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

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 5804kb

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: 1440ms
memory: 47432kb

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