QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201030#5020. 举办乘凉州喵,举办乘凉州谢谢喵hos_lyric#0 465ms4804kbC++1412.2kb2023-10-05 07:15:362024-07-04 02:16:05

Judging History

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

  • [2024-07-04 02:16:05]
  • 评测
  • 测评结果:0
  • 用时:465ms
  • 内存:4804kb
  • [2023-10-05 07:15:36]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


struct Hld {
  int n, rt;
  // needs to be tree
  // vertex lists
  // modified in build(rt) (parent removed, heavy child first)
  vector<vector<int>> graph;
  vector<int> sz, par, dep;
  int zeit;
  vector<int> dis, fin, sid;
  // head vertex (minimum depth) in heavy path
  vector<int> head;

  Hld() : n(0), rt(-1), zeit(0) {}
  explicit Hld(int n_) : n(n_), rt(-1), graph(n), zeit(0) {}
  void ae(int u, int v) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  void dfsSz(int u) {
    sz[u] = 1;
    for (const int v : graph[u]) {
      auto it = std::find(graph[v].begin(), graph[v].end(), u);
      if (it != graph[v].end()) graph[v].erase(it);
      par[v] = u;
      dep[v] = dep[u] + 1;
      dfsSz(v);
      sz[u] += sz[v];
    }
  }
  void dfsHld(int u) {
    dis[u] = zeit++;
    const int deg = graph[u].size();
    if (deg > 0) {
      int vm = graph[u][0];
      int jm = 0;
      for (int j = 1; j < deg; ++j) {
        const int v = graph[u][j];
        if (sz[vm] < sz[v]) {
          vm = v;
          jm = j;
        }
      }
      swap(graph[u][0], graph[u][jm]);
      head[vm] = head[u];
      dfsHld(vm);
      for (int j = 1; j < deg; ++j) {
        const int v = graph[u][j];
        head[v] = v;
        dfsHld(v);
      }
    }
    fin[u] = zeit;
  }
  void build(int rt_) {
    assert(0 <= rt_); assert(rt_ < n);
    rt = rt_;
    sz.assign(n, 0);
    par.assign(n, -1);
    dep.assign(n, -1);
    dep[rt] = 0;
    dfsSz(rt);
    zeit = 0;
    dis.assign(n, -1);
    fin.assign(n, -1);
    head.assign(n, -1);
    head[rt] = rt;
    dfsHld(rt);
    assert(zeit == n);
    sid.assign(n, -1);
    for (int u = 0; u < n; ++u) sid[dis[u]] = u;
  }

  friend ostream &operator<<(ostream &os, const Hld &hld) {
    const int maxDep = *max_element(hld.dep.begin(), hld.dep.end());
    vector<string> ss(2 * maxDep + 1);
    int pos = 0, maxPos = 0;
    for (int j = 0; j < hld.n; ++j) {
      const int u = hld.sid[j];
      const int d = hld.dep[u];
      if (hld.head[u] == u) {
        if (j != 0) {
          pos = maxPos + 1;
          ss[2 * d - 1].resize(pos, '-');
          ss[2 * d - 1] += '+';
        }
      } else {
        ss[2 * d - 1].resize(pos, ' ');
        ss[2 * d - 1] += '|';
      }
      ss[2 * d].resize(pos, ' ');
      ss[2 * d] += std::to_string(u);
      if (maxPos < static_cast<int>(ss[2 * d].size())) {
        maxPos = ss[2 * d].size();
      }
    }
    for (int d = 0; d <= 2 * maxDep; ++d) os << ss[d] << '\n';
    return os;
  }

  bool contains(int u, int v) const {
    return (dis[u] <= dis[v] && dis[v] < fin[u]);
  }
  int lca(int u, int v) const {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    for (; head[u] != head[v]; ) (dis[u] > dis[v]) ? (u = par[head[u]]) : (v = par[head[v]]);
    return (dis[u] > dis[v]) ? v : u;
  }
  int jumpUp(int u, int d) const {
    assert(0 <= u); assert(u < n);
    assert(d >= 0);
    if (dep[u] < d) return -1;
    const int tar = dep[u] - d;
    for (u = head[u]; ; u = head[par[u]]) {
      if (dep[u] <= tar) return sid[dis[u] + (tar - dep[u])];
    }
  }
  int jump(int u, int v, int d) const {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    assert(d >= 0);
    const int l = lca(u, v);
    const int du = dep[u] - dep[l], dv = dep[v] - dep[l];
    if (d <= du) {
      return jumpUp(u, d);
    } else if (d <= du + dv) {
      return jumpUp(v, du + dv - d);
    } else {
      return -1;
    }
  }
  // [u, v) or [u, v]
  template <class F> void doPathUp(int u, int v, bool inclusive, F f) const {
    assert(contains(v, u));
    for (; head[u] != head[v]; u = par[head[u]]) f(dis[head[u]], dis[u] + 1);
    if (inclusive) {
      f(dis[v], dis[u] + 1);
    } else {
      if (v != u) f(dis[v] + 1, dis[u] + 1);
    }
  }
  // not path order, include lca(u, v) or not
  template <class F> void doPath(int u, int v, bool inclusive, F f) const {
    const int l = lca(u, v);
    doPathUp(u, l, false, f);
    doPathUp(v, l, inclusive, f);
  }

  // (vs, ps): compressed tree
  // vs: DFS order (sorted by dis)
  // vs[ps[x]]: the parent of vs[x]
  // ids[vs[x]] = x, not set for non-tree vertex
  vector<int> ids;
  pair<vector<int>, vector<int>> compress(vector<int> us) {
    // O(n) first time
    ids.resize(n, -1);
    std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
      return (dis[u] < dis[v]);
    });
    us.erase(std::unique(us.begin(), us.end()), us.end());
    int usLen = us.size();
    assert(usLen >= 1);
    for (int x = 1; x < usLen; ++x) us.push_back(lca(us[x - 1], us[x]));
    std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
      return (dis[u] < dis[v]);
    });
    us.erase(std::unique(us.begin(), us.end()), us.end());
    usLen = us.size();
    for (int x = 0; x < usLen; ++x) ids[us[x]] = x;
    vector<int> ps(usLen, -1);
    for (int x = 1; x < usLen; ++x) ps[x] = ids[lca(us[x - 1], us[x])];
    return make_pair(us, ps);
  }
};

////////////////////////////////////////////////////////////////////////////////


int N;
vector<int> A, B;
int Q;
vector<int> X, Y, D;

vector<vector<int>> graph;
Hld hld;


namespace brute {
vector<int> run() {
cerr<<"[brute::run]"<<endl;
  vector<int> ans(Q, 0);
  for (int q = 0; q < Q; ++q) {
    const int x = X[q], y = Y[q];
    const int l = hld.lca(x, y);
    queue<int> que;
    vector<int> dist(N, -1);
    auto reach = [&](int v, int c) -> void {
      if (!~dist[v]) {
        dist[v] = c;
        que.push(v);
      }
    };
    for (int u = x; u != l; u = hld.par[u]) reach(u, 0);
    for (int u = y; u != l; u = hld.par[u]) reach(u, 0);
    reach(l, 0);
    for (; !que.empty(); ) {
      const int u = que.front();
      que.pop();
      for (const int v : graph[u]) reach(v, dist[u] + 1);
    }
    for (int u = 0; u < N; ++u) if (dist[u] <= D[q]) {
      ++ans[q];
    }
  }
  return ans;
}
}  // brute


namespace sub3 {
vector<vector<pair<int, pair<int, int>>>> ess;
vector<int> ans;

vector<int> sz, del;
void dfsSz(int u, int p) {
  sz[u] = 1;
  for (const int v : graph[u]) if (p != v) {
    dfsSz(v, u);
    sz[u] += sz[v];
  }
}
string dfsString(int u, int p) {
  ostringstream oss;
  oss << "[" << u;
  for (const int v : graph[u]) if (!del[v] && p != v) {
    oss << " " << dfsString(v, u);
  }
  oss << "]";
  return oss.str();
}
/// vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vector<int> par, dep;
vector<vector<int>> uss, fss;
void dfs(int j, int u, int p, int d) {
  par[u] = p;
  dep[u] = d;
  uss[j].push_back(u);
  if ((int)fss[j].size() < d + 1) fss[j].resize(d + 1, 0);
  ++fss[j][d];
  for (const int v : graph[u]) if (!del[v] && p != v) {
    dfs(j, v, u, d + 1);
  }
}
/// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
void solveSubtree(int depth, int r) {
#ifdef LOCAL
  cerr << string(2 * depth, ' ') << "solveSubtree " << dfsString(r, -1) << endl;
#endif
  vector<int> vs;
  for (const int v : graph[r]) if (!del[v]) {
    vs.push_back(v);
  }
  const int len = vs.size();
  /// vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
  sort(vs.begin(), vs.end());
  uss.assign(len, {});
  fss.assign(len + 1, vector<int>(2, 0));
  for (int j = 0; j < len; ++j) {
    dfs(j, vs[j], r, 1);
  }
  int mx = 2;
  for (int j = 0; j < len; ++j) {
    chmax(mx, (int)fss[j].size());
  }
  fss[len].assign(mx, 0);
  par[r] = -1;
  dep[r] = 0;
  ++fss[len][0];
  for (int j = 0; j < len; ++j) {
    for (int d = 0; d < (int)fss[j].size(); ++d) {
      fss[len][d] += fss[j][d];
    }
  }
  for (int j = 0; j <= len; ++j) {
    for (int d = 1; d < (int)fss[j].size(); ++d) {
      fss[j][d] += fss[j][d - 1];
    }
  }
// cerr<<string(2*depth,' ')<<"uss = "<<uss<<", fss = "<<fss<<endl;
  auto get = [&](int j, int d) -> int {
    return fss[j][min(d, (int)fss[j].size() - 1)];
  };
  for (const auto &e : ess[r]) {
    const int q = e.first;
    ans[q] += get(len, D[q]);
    for (const int v : {e.second.first, e.second.second}) {
      const int j = lower_bound(vs.begin(), vs.end(), v) - vs.begin();
      if (j < len && vs[j] == v) {
        ans[q] -= get(j, D[q]);
      }
    }
  }
  for (int j = 0; j < len; ++j) {
    for (const int u : uss[j]) {
      for (const auto &e : ess[u]) {
        const int q = e.first;
        if (par[u] != e.second.first && par[u] != e.second.second && dep[u] <= D[q]) {
          ans[q] += get(len, D[q] - dep[u]);
          ans[q] -= get(j, D[q] - dep[u]);
        }
      }
    }
  }
  /// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
}
void solveRec(int depth, int u) {
  for (; ; ) {
    int vm = -1;
    for (const int v : graph[u]) if (!del[v]) {
      if (!~vm || sz[vm] < sz[v]) {
        vm = v;
      }
    }
    if (!~vm || 2 * sz[vm] <= sz[u]) {
      solveSubtree(depth, u);
      del[u] = 1;
      for (const int v : graph[u]) if (!del[v]) {
        solveRec(depth + 1, v);
      }
      break;
    } else {
      sz[u] -= sz[vm];
      sz[vm] += sz[u];
      u = vm;
    }
  }
}
void centroidDecomp() {
  sz.assign(N, 0);
  dfsSz(0, -1);
  del.assign(N, 0);
  par.resize(N);
  dep.resize(N);
  solveRec(0, 0);
}

vector<int> run() {
cerr<<"[sub3::run]"<<endl;
  ess.assign(N, {});
  for (int q = 0; q < Q; ++q) {
    const int x = X[q], y = Y[q];
    const int l = hld.lca(x, y);
    vector<int> us, vs;
    for (int u = x; u != l; u = hld.par[u]) us.push_back(u);
    us.push_back(l);
    for (int u = y; u != l; u = hld.par[u]) vs.push_back(u);
    reverse(vs.begin(), vs.end());
    us.insert(us.end(), vs.begin(), vs.end());
    const int usLen = us.size();
// cerr<<us<<endl;
    for (int j = 0; j < usLen; ++j) {
      const int uL = (j - 1 >= 0) ? us[j - 1] : -1;
      const int u = us[j];
      const int uR = (j + 1 < usLen) ? us[j + 1] : -1;
      ess[u].emplace_back(q, make_pair(uL, uR));
    }
  }
  ans.assign(Q, 0);
  centroidDecomp();
  return ans;
}
}  // sub3


int main() {
  for (; ~scanf("%d", &N); ) {
    A.resize(N - 1);
    B.resize(N - 1);
    for (int i = 0; i < N - 1; ++i) {
      scanf("%d%d", &A[i], &B[i]);
      --A[i];
      --B[i];
    }
    scanf("%d", &Q);
    X.resize(Q);
    Y.resize(Q);
    D.resize(Q);
    for (int q = 0; q < Q; ++q) {
      scanf("%d%d%d", &X[q], &Y[q], &D[q]);
      --X[q];
      --Y[q];
    }
    
    graph.assign(N, {});
    hld = Hld(N);
    for (int i = 0; i < N - 1; ++i) {
      graph[A[i]].push_back(B[i]);
      graph[B[i]].push_back(A[i]);
      hld.ae(A[i], B[i]);
    }
    hld.build(0);
    
    vector<int> ans;
    if (N <= 5000 && Q <= 5000) {
      ans = brute::run();
    } else {
      ans = sub3::run();
    }
    for (int q = 0; q < Q; ++q) {
      printf("%d\n", ans[q]);
    }
  }
  return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 7
Accepted
time: 427ms
memory: 4716kb

input:

4988
1 2
1 3
1 4
4 5
1 6
3 7
3 8
5 9
4 10
6 11
3 12
9 13
11 14
8 15
11 16
1 17
7 18
8 19
18 20
7 21
10 22
15 23
18 24
4 25
24 26
9 27
23 28
3 29
3 30
30 31
11 32
18 33
2 34
32 35
29 36
29 37
19 38
9 39
6 40
25 41
16 42
31 43
6 44
42 45
32 46
27 47
32 48
44 49
7 50
10 51
24 52
46 53
30 54
46 55
39 56...

output:

3226
2028
4988
208
252
3970
3886
2013
4974
2118
308
391
4768
312
4954
4988
4974
1551
4981
12
1856
4825
4974
4974
19
82
4960
4680
208
4870
474
3693
808
1880
213
3394
1203
266
84
4822
3334
70
81
4501
4960
668
4866
4974
113
490
75
163
209
2159
4981
4143
100
3168
232
66
4864
525
4958
390
4713
2305
15
49...

result:

ok 4966 numbers

Test #2:

score: 0
Accepted
time: 215ms
memory: 4544kb

input:

4914
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
27 ...

output:

3378
4914
231
4914
4914
3378
22
4914
4914
2559
4914
75
219
1407
1138
863
24
3890
4914
4914
399
399
13
139
77
4914
4095
3071
4914
23
151
110
1407
43
54
4914
4914
1919
2559
77
735
3071
24
133
479
4914
33
831
4
4914
4914
79
4914
199
3890
3071
73
567
15
75
21
126
4914
4914
203
4914
75
127
62
41
4914
409...

result:

ok 4975 numbers

Test #3:

score: -7
Wrong Answer
time: 465ms
memory: 4804kb

input:

4921
1151 2767
2767 322
322 4451
4451 4867
4867 1265
1265 3197
3197 3890
3890 1052
1052 1407
1407 1578
1578 566
566 2965
2965 260
260 4908
4908 308
308 553
553 2845
2845 4249
4249 1284
1284 73
73 1088
1088 277
277 1878
1878 4128
4128 3609
3609 2126
2126 149
149 3467
3467 1653
1653 4913
4913 3604
360...

output:


result:

wrong output format Output file not found: ""

Subtask #2:

score: 0
Judgement Failed

Test #9:

score: 0
Judgement Failed

input:


output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Judgement Failed

Test #25:

score: 0
Judgement Failed

input:


output:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%