QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113034#4814. Exciting Travelnhuang685WA 1ms3580kbC++209.1kb2023-06-16 01:50:082023-06-16 01:50:11

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-16 01:50:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3580kb
  • [2023-06-16 01:50:08]
  • 提交

answer

/**
 * @file qoj4814F1.cpp
 * @author nhuang685
 * @brief
 * @date 2023-06-15
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
std::ifstream cin;
std::ofstream cout;
using std::cerr;
#else
using std::cin;
using std::cout;
#define cerr \
  if (false) std::cerr
#endif

template <class T>
class RSegB {
 protected:
  int sz;
  std::vector<T> val;

  virtual void push(int ind, int l, int r) = 0;
  virtual void initLazy() = 0;
  void pull(int ind) { val[ind] = comb(val[2 * ind], val[2 * ind + 1]); }

  template <class F>
  void modify(int a, int b, const T &v, const F &addToLazy, int ind, int l,
              int r) {
    push(ind, l, r);
    if (a <= l && r <= b) {
      addToLazy(ind, v);
      push(ind, l, r);
      return;
    } else if (b < l || r < a)
      return;

    int mid = (l + r) / 2;
    modify(a, b, v, addToLazy, 2 * ind, l, mid);
    modify(a, b, v, addToLazy, 2 * ind + 1, mid + 1, r);

    pull(ind);
  }
  T query(int a, int b, int ind, int l, int r) {
    push(ind, l, r);
    if (a <= l && r <= b)
      return val[ind];
    else if (b < l || r < a)
      return ID();

    int mid = (l + r) / 2;
    return comb(query(a, b, 2 * ind, l, mid),
                query(a, b, 2 * ind + 1, mid + 1, r));
  }

 public:
  virtual T ID() = 0;
  virtual T comb(const T &a, const T &b) = 0;
  void init(int _sz) {
    sz = 1;
    while (sz < _sz) sz *= 2;
    val.resize(2 * sz, ID());
    initLazy();
  }
  void init(const std::vector<T> &arr) {
    init((int)arr.size());
    for (int i = 0; i < (int)arr.size(); ++i) {
      val[i + sz] = arr[i];
    }
    for (int i = sz - 1; i >= 1; --i) pull(i);
  }

  T query(int a, int b) { return query(a, b, 1, 0, sz - 1); }
};
template <class T>
class LSeg : public RSegB<T> {
 private:
  std::vector<T> ls;
  void push(int ind, int l, int r) {
    if (ls[ind] == ID2()) return;
    RSegB<T>::val[ind] = (r - l + 1) * ls[ind];
    if (l != r) {
      ls[2 * ind] = ls[ind];
      ls[2 * ind + 1] = ls[ind];
    }
    ls[ind] = ID2();
  }
  void initLazy() { ls.resize(2 * RSegB<T>::sz, ID2()); }

 public:
  T ID() { return 0; }
  T ID2() { return -1; }  // change ID2 if necessary
  T comb(const T &a, const T &b) { return a + b; }
  void set(int a, int b, T v) {
    RSegB<T>::modify(
        a, b, v, [this](int ind, const T &value) { ls[ind] = value; }, 1, 0,
        RSegB<T>::sz - 1);
  }
  void set(int i, T v) { set(i, i, v); }
};
template <class T, class RangeQ>
class HLDB {
  // code based on https://codeforces.com/blog/entry/22072
 protected:
  int N;
  std::vector<int> p, r, h, d, ind;
  RangeQ seg;
  bool edge;
  int init(int node, const std::vector<std::vector<int>> &adj) {
    int heavySz = -1, sz = 1;
    for (int i : adj[node]) {
      if (i == p[node]) continue;
      p[i] = node;
      d[i] = d[node] + 1;
      int cSz = init(i, adj);
      sz += cSz;
      if (cSz > heavySz) {
        heavySz = cSz;
        h[node] = i;
      }
    }
    return sz;
  }
  template <class F>
  void upd(int i, const F &f) {
    f(ind[i]);
  }
  template <class F>
  void upd(int u, int v, const F &f) {
    for (; r[u] != r[v]; v = p[r[v]]) {
      if (d[r[u]] > d[r[v]]) std::swap(u, v);
      f(ind[r[v]], ind[v]);
    }
    if (d[u] > d[v]) std::swap(u, v);
    f(ind[u], ind[v]);
  }

 public:
  void init(const std::vector<std::vector<int>> &adj) {
    N = static_cast<int>(adj.size());
    p.assign(N, -1);
    h.assign(N, -1);
    d.assign(N, 0);
    init(0, adj);

    r.assign(N, -1);
    ind.assign(N, 0);
    int cnt = 0;
    for (int i = 0; i < N; ++i)
      if (p[i] == -1 || h[p[i]] != i)
        for (int j = i; j != -1; j = h[j]) {
          r[j] = i;
          ind[j] = cnt++;
        }
    seg.init(N);
  }

  T query(int i, int j) {
    T res = seg.ID();
    upd(i, j,
        [this, &res](int u, int v) { res = seg.comb(res, seg.query(u, v)); });
    return res;
  }
  int lca(int u, int v) {
    for (; r[u] != r[v]; v = p[r[v]]) {
      if (d[r[u]] > d[r[v]]) std::swap(u, v);
    }
    if (d[u] > d[v]) std::swap(u, v);
    return u;
  }
};
template <class T>
class SegB {
 protected:
  int sz;
  std::vector<T> val;
  virtual T ID() = 0;
  virtual T comb(const T &a, const T &b) = 0;
  void pull(int ind) { val[ind] = comb(val[2 * ind], val[2 * ind + 1]); }

  template <class F>
  void upd(int i, const T &a, const F &add) {
    add(i += sz, a);
    for (i /= 2; i >= 1; i /= 2) pull(i);
  }

 public:
  void init(int _sz) {
    sz = 1;
    while (sz < _sz) sz *= 2;
    val.assign(2 * sz, ID());
  }
  void init(const std::vector<T> &arr) {
    init(static_cast<int>(arr.size()));
    for (int i = 0; i < static_cast<int>(arr.size()); ++i) {
      val[i + sz] = arr[i];
    }
    for (int i = sz - 1; i >= 1; --i) pull(i);
  }

  void set(int i, const T &a) {
    upd(i, a, [this](int ind, const T &v) { val[ind] = v; });
  }
  T query(int i, int j) {
    T l = ID(), r = ID();
    for (i += sz, j += sz; i <= j; i /= 2, j /= 2) {
      if (i % 2 == 1) l = comb(val[i++], l);
      if (j % 2 == 0) r = comb(r, val[j--]);
    }
    return comb(l, r);
  }
};
template <class T>
class HLD : public HLDB<T, LSeg<T>> {
  using B = HLDB<T, LSeg<T>>;

 public:
  void set(int i, const T &v) {
    B::upd(i, [this, &v](int u) { B::seg.set(u, v); });
  }
  void set(int a, int b, const T &v) {
    B::upd(a, b, [this, &v](int u, int j) { B::seg.set(u, j, v); });
  }
};
class Tour {
 private:
  template <class T>
  class Seg : public SegB<T> {
   public:
    constexpr static T id = {(int)1e9, (int)1e9};
    T ID() { return id; }
    T comb(const T &a, const T &b) { return std::min(a, b); }
    void add(int i, const T &a) {
      SegB<T>::upd(i, a,
                   [this](int ind, const T &v) { SegB<T>::val[ind] += v; });
    }
  };
  std::vector<int> ind, d;
  int sz;
  Seg<std::pair<int, int>> seg;
  void dfs(int node, int par, const std::vector<std::vector<int>> &adj,
           std::vector<std::pair<int, int>> &t) {
    ind[node] = (int)t.size();
    t.emplace_back(d[node], node);
    for (int i : adj[node]) {
      if (i == par) continue;
      d[i] = d[node] + 1;
      dfs(i, node, adj, t);
      t.emplace_back(d[node], node);
    }
  }

 public:
  Tour(const std::vector<std::vector<int>> &adj) {
    sz = (int)adj.size();
    std::vector<std::pair<int, int>> t;
    ind.resize(sz);
    d.resize(sz);
    dfs(0, -1, adj, t);
    seg.init(t);
  }
  int lca(int u, int v) {
    return seg.query(std::min(ind[u], ind[v]), std::max(ind[u], ind[v])).second;
  }
  const int &operator[](int i) { return ind[i]; }
  int depth(int i) { return d[i]; }
  int size() { return sz; }
};
class VT {
 private:
  Tour &t;
  int sz, cnt = 0;
  std::vector<int> ind;
  std::vector<std::vector<int>> vtadj;
  std::vector<int> p;

 public:
  VT(Tour &_t) : t(_t), sz(_t.size()), ind(_t.size()) {}
  void init(std::vector<int> v) {
    v.push_back(0);
    std::sort(v.begin(), v.end(), [this](int a, int b) { return t[a] < t[b]; });
    v.erase(std::unique(v.begin(), v.end()), v.end());
    int vsz = (int)v.size();
    for (int i = 0; i < vsz - 1; ++i) v.push_back(t.lca(v[i], v[i + 1]));
    std::sort(v.begin(), v.end(), [this](int a, int b) { return t[a] < t[b]; });
    v.erase(std::unique(v.begin(), v.end()), v.end());

    for (cnt = 0; cnt < (int)v.size(); ++cnt) ind[v[cnt]] = cnt;
    vtadj.resize(cnt);
    p.resize(cnt);

    std::stack<int> s;
    for (int node : v) {
      if (!vtadj[ind[node]].empty()) vtadj[ind[node]].clear();
      if (node == 0) {
        s.push(0);
        continue;
      }
      int par = t.lca(s.top(), node);
      while (!s.empty() && t.depth(par) <= t.depth(s.top())) s.pop();
      if (t.depth(par) < t.depth(node)) {
        vtadj[ind[par]].push_back(ind[node]);
        vtadj[ind[node]].push_back(ind[par]);
        p[ind[node]] = ind[par];
      }
      s.push(node);
    }
  }

  const auto &operator[](int node) { return ind[node]; }
  const auto &adj(int node) { return vtadj[ind[node]]; }
  const auto &adj() { return vtadj; }
  int par(int i) { return p[ind[i]]; }
};

int main() {
#ifdef LOCAL
  cin.open("input.txt");
  cout.rdbuf()->pubsetbuf(0, 0);
  cout.open("output.txt");
#else
  cin.tie(nullptr)->sync_with_stdio(false);
#endif

  int n, m;
  cin >> n >> m;

  std::vector<std::vector<int>> adj(n);
  for (int i = 0; i < n - 1; ++i) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }

  Tour t(adj);
  VT vt(t);

  while (m--) {
    int k;
    cin >> k;
    std::vector<int> x(k);
    for (int i = 0; i < k; ++i) cin >> x[i], x[i]--;
    vt.init(x);
    HLD<int> im;
    HLD<int> v;

    int ans = 0;
    im.init(vt.adj());
    v.init(vt.adj());
    for (int i : x) im.set(vt[i], 1);
    for (int i = 0; i < k - 1; ++i) {
      int a = vt[x[i]], b = vt[x[i + 1]];
      if (im.query(a, b) > 2 || v.query(a, b) > 1) {
        ans++;
        v.set(a, 1);
        v.set(b, 1);
      } else
        v.set(a, b, 1);
    }
    cout << ans << '\n';
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 3
1 2
1 3
2 4
2 5
3 1 4 5
4 1 2 4 3
4 2 4 5 1

output:

1
1
2

result:

ok 3 number(s): "1 1 2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

8 7
1 2
1 3
1 4
2 5
2 6
5 7
3 8
1 4
2 1 7
3 5 2 4
4 3 6 1 4
6 5 3 7 1 2 4
6 4 8 3 5 6 1
7 2 8 5 4 6 1 3

output:

0
0
0
1
4
3
5

result:

ok 7 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

10 10
8 3
10 4
1 2
10 9
9 1
4 8
1 5
6 3
2 7
1 10
1 3
5 4 6 8 3 10
5 1 6 3 8 7
1 5
4 3 8 1 4
1 10
3 4 6 9
1 6
3 7 5 3

output:

0
0
3
2
0
1
0
1
0
1

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 3484kb

input:

1 1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3472kb

input:

1 0

output:


result:

ok 0 number(s): ""

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 3520kb

input:

20 15
9 4
3 9
10 9
7 14
2 1
16 13
15 20
6 1
8 11
18 19
20 3
12 7
9 17
7 13
8 5
19 20
10 12
1 8
9 8
3 8 12 15
2 5 4
6 17 4 8 7 5 18
1 7
1 18
2 2 20
5 13 6 5 15 17
1 6
1 9
7 4 15 3 2 9 5 13
2 16 18
2 2 6
2 5 17
8 1 11 8 12 9 18 13 17
7 5 6 13 1 11 18 9

output:

1
0
4
0
0
0
3
0
0
4
0
0
0
4
4

result:

wrong answer 7th numbers differ - expected: '2', found: '3'