QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#177551#7103. Red Black TreesilxiAC ✓653ms51356kbC++206.2kb2023-09-13 03:39:312023-09-13 03:39:31

Judging History

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

  • [2023-09-13 03:39:31]
  • 评测
  • 测评结果:AC
  • 用时:653ms
  • 内存:51356kb
  • [2023-09-13 03:39:31]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

namespace superIO {
  int BUF=100000;
  int buf_readed = 0;
  int buf_index = 0;
  char buffer[100000];
  /*****************************************/
  char my_getchar(){
    char x;
    if(buf_index==buf_readed){
      buf_index=0;
      buf_readed=fread(buffer,1,BUF,stdin);
    }
    x=buffer[buf_index];
    buf_index++;
    return x;
  }
  /*************************************/

  //can return int or long long
  int getInt(){
    int r=0;
    char c;
    int sign=1;
    while(1){
      c=my_getchar();
      if(c=='-')
        sign=-1;

      if((c>='0' && c<='9')){
        r=(c-'0');
        break;
      }
    }
    while(1){
      c=my_getchar();
      if(!(c>='0' && c<='9'))
        break;
      r=r*10+(c-'0');
    }
    return sign*r;
  }
}
using namespace superIO;

// Template {{{
#define REP(n) for (int _=0; _<(n); _++)
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

namespace std {
  template<class Fun>
  class y_combinator_result {
    Fun fun_;
  public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
   
    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
      return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
  };
   
  template<class Fun>
  decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
  }
} // namespace std

#define DEBUG(x) cerr << #x << ": " << x << '\n'
template<typename A, typename B> 
ostream& operator<<(ostream &os, const pair<A, B> &p) { 
  return os << '(' << p.first << ", " << p.second << ')'; 
}
template<typename T_container, 
  typename T = typename enable_if<!is_same<T_container, string>::value, 
  typename T_container::value_type>::type> 
ostream& operator<<(ostream &os, const T_container &v) { 
  os << '['; string sep; 
  for (const T &x : v) 
    os << sep << x, sep = ", "; 
  return os << ']'; 
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// }}}

// Data structure for handling LCA queries and preorder traversals.
pair<int, int> mincomp(pair<int, int> x, pair<int, int> y) {
  return min(x, y);
}

// combine should be associative and idempotent (e.g., min, max, gcd)
template<typename T, T (*combine)(T, T)>
struct SparseTable
{
  int n, maxk;
  vector<vector<T>> tb;
  static inline int lg(int x) { return 32 - __builtin_clz(x) - 1; }
  SparseTable() {}
  SparseTable(const vector<T>& a) : n(sz(a)) {
    maxk = 0;
    while (n >= (1<<maxk)) maxk++;
    tb.resize(maxk, vector<T>(n));
    for (int i = 0; i < n; i++) tb[0][i] = a[i];
    for (int k = 1; k <= lg(n); k++) {
      for (int i = 0; i < n; i++) {
        int nx = i + (1<<(k-1));
        if (nx < n) tb[k][i] = combine(tb[k-1][i], tb[k-1][nx]);
        else tb[k][i] = tb[k-1][i];
      }
    }
  }
  T prod(int l, int r) {
    int g = lg(r-l+1);
    return combine(tb[g][l], tb[g][r-(1<<g)+1]);
  }
};

struct Tree {
  int n, maxk;
  bool is_0_index;
  vector<bool> isRed;
  vector<vector<pair<int, ll>>> adj;
  vector<int> udepth;
  vector<ll> depth, depthFromRed;
  vector<pair<int, int>> E;
  vector<int> Eindex;
  int e_idx = 0;
  SparseTable<pair<int, int>, mincomp> table;

  void dfs(int i, int p, int& t, ll nearestRedDepth) {
    Eindex[i] = e_idx;
    E[e_idx++] = {udepth[i], i};
    depthFromRed[i] = depth[i] - nearestRedDepth;
    for (auto [j, w]: adj[i]) if (j != p) {
        udepth[j] = udepth[i] + 1;
        depth[j] = depth[i] + w;
        dfs(j, i, t, isRed[i] ? depth[i] : nearestRedDepth);
        E[e_idx++] = {udepth[i], i};
      }
  }

  Tree(int _n, bool _is_0_index = true) : n(_n), is_0_index(_is_0_index) {
    maxk = 0;
    while (n >= (1<<maxk)) maxk++;
    int sz = is_0_index ? n : n+1;
    isRed.resize(sz, false);
    adj.resize(sz);
    udepth.resize(sz, 0);
    depth.resize(sz, 0);
    depthFromRed.resize(sz, 0);
    E.resize(2*sz-1);
    Eindex.resize(sz, -1);
    e_idx = 0;
  }
  void add_edge(int u, int v, ll w) {
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }

  void init() {
    int root = is_0_index ? 0 : 1;
    int t = 0;
    dfs(root, -1, t, 0);
    table = SparseTable<pair<int, int>, mincomp>(E);
  }

  int lca(int a, int b) {
    int i = Eindex[a], j = Eindex[b];
    if (i > j) swap(i, j);
    return table.prod(i, j).second;
  }
};

void solve() {
  int N = getInt(), M = getInt(), Q = getInt();
  // int N, M, Q; cin >> N >> M >> Q;
  Tree tree(N);
  F0R(i, M) {
    int x = getInt(); x--;
    // int x; cin >> x; x--;
    tree.isRed[x] = 1;
  }
  REP(N-1) {
    int u = getInt(), v = getInt(), w = getInt();
    // int u, v, w; cin >> u >> v >> w;
    u--, v--;
    tree.add_edge(u, v, w);
  }
  tree.init();

  vector<pair<ll, int>> ks(N);
  auto query = [&](int sz) -> ll {
    if (sz == 0) return 0;
    ll ans = ks.front().first;
    int lc = ks.front().second;
    ll curd = 0;
    F0R(idx, sz) {
      auto [d, i] = ks[idx];
      int lcN = tree.lca(lc, i);
      curd = max(curd + tree.depth[lc] - tree.depth[lcN],
                 tree.depth[i] - tree.depth[lcN]);
      ll tr = max(curd, idx + 1 < sz ? ks[idx+1].first : 0);
      ckmin(ans, tr);
      lc = lcN;
    }
    return ans;
  };

  REP(Q) {
    int k = getInt();
    // int k; cin >> k;
    int c = 0;
    REP(k) {
      int x = getInt(); x--;
      // int x; cin >> x; x--;
      if (!tree.isRed[x])
        ks[c++] = {tree.depthFromRed[x], x};
    }
    sort(ks.begin(), ks.begin() + c, greater());
    // printf("%lld\n", query(c));
    cout << query(c) << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  int T = getInt();
  // int T; cin >> T;
  while (T--) solve();
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 653ms
memory: 51356kb

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