QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#773186#7103. Red Black TreeMiguel03121WA 681ms35912kbC++173.1kb2024-11-23 03:36:242024-11-23 03:36:25

Judging History

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

  • [2024-11-23 03:36:25]
  • 评测
  • 测评结果:WA
  • 用时:681ms
  • 内存:35912kb
  • [2024-11-23 03:36:24]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define F(i, a, b) for (int i = a; i < b; i++)
#define ALL(x) x.begin(), x.end()
#define IOS ios_base::sync_with_stdio(0)

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;

template <class T> struct RMQ {
  vector<vector<T>> jmp;
  RMQ(const vector<T> &V) : jmp(1, V) {
    for (int pw = 1, k = 1; pw * 2 <= V.size(); pw *= 2, ++k) {
      jmp.emplace_back(V.size() - pw * 2 + 1);
      for (int j = 0; j < jmp[k].size(); j++) {
        jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
      }
    }
  }

  T query(int a, int b) {
    int dep = 31 - __builtin_clz(b - a);
    return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
  }
};

struct LCA {
  int T = 0;
  vi time, path, ret;
  RMQ<int> rmq;

  LCA(vector<vector<pair<int, ll>>> &C)
      : time(C.size()), rmq((dfs(C, 0, -1), ret)) {}

  void dfs(vector<vector<pair<int, ll>>> &C, int v, int par) {
    time[v] = T++;
    for (auto &x : C[v]) {
      int y = x.first;
      if (y != par) {
        path.push_back(v), ret.push_back(time[v]);
        dfs(C, y, v);
      }
    }
  }

  int lca(int a, int b) {
    if (a == b)
      return a;
    tie(a, b) = minmax(time[a], time[b]);
    return path[rmq.query(a, b)];
  }
};

vector<bool> red;
vector<vector<pair<int, ll>>> adj;
vector<ll> depth, best;

void dfs(int cur, int p) {
  for (auto u : adj[cur]) {
    if (u.first == p) {
      continue;
    }
    depth[u.first] = depth[cur] + u.second;
    if (red[u.first]) {
      best[u.first] = 0;
    } else {
      best[u.first] = best[cur] + u.second;
    }
    dfs(u.first, cur);
  }
}

signed main() {
  IOS;
  cin.tie(0), cout.tie(0);

  int t, n, m, q;
  cin >> t;
  while (t--) {
    cin >> n >> m >> q;
    red = vector<bool>(n);
    ll u, v, d;
    F(i, 0, m) {
      cin >> u;
      u--;
      red[u] = true;
    }
    adj = vector<vector<pair<int, ll>>>(n);
    F(i, 0, n - 1) {
      cin >> u >> v >> d;
      u--, v--;
      adj[u].push_back({v, d});
      adj[v].push_back({u, d});
    }

    LCA lca(adj);
    best = vector<ll>(n), depth = vector<ll>(n);
    dfs(0, -1);

    int k;
    while (q--) {
      cin >> k;
      priority_queue<pair<ll, int>> pq;
      while (k--) {
        cin >> u;
        u--;
        pq.push({best[u], u});
      }

      ll curNode = pq.top().second;
      ll maxDepth = depth[curNode];
      pq.pop();
      ll ans = (pq.empty() ? 0 : pq.top().first);
      while (!pq.empty()) {
        u = pq.top().second;
        pq.pop();
        curNode = lca.lca(curNode, u);
        maxDepth = max(maxDepth, depth[u]);
        ll tmp = maxDepth - depth[curNode];
        // cout << curNode << ' ' << u << ' ' << maxDepth << ' ' << tmp << endl;
        if (pq.empty()) {
          ans = min(ans, tmp);
        } else if (tmp <= pq.top().first) {
          ans = min(ans, pq.top().first);
        }
      }
      cout << ans << '\n';
    }
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3784kb

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: -100
Wrong Answer
time: 681ms
memory: 35912kb

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:

151364130
151364130
0
319801028
319801028
255904892
317070839
1265145897
1265145897
1168076167
1168076167
455103436
285643094
285643094
285643094
317919339
0
785245841
691421476
605409472
479058444
371688030
307718947
493383271
1107439380
910180170
1124931652
121535083
316895493
316895493
316895493
...

result:

wrong answer 1st lines differ - expected: '148616264', found: '151364130'