QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#397816#8546. Min or Max 2comeintocalm#RE 0ms0kbC++202.3kb2024-04-24 17:16:122024-04-24 17:16:13

Judging History

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

  • [2024-04-24 17:16:13]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-04-24 17:16:12]
  • 提交

answer

#include <bits/stdc++.h>

const int N = 1e5 + 5;

int n, q;
struct SegTree {
  int a[N];
  void insert(int p, int k) {
    for (; p <= n; p += (p & -p)) {
      a[p] += k;
    }
  }
  int ask(int p, int ret = 0) {
    for (; p; p -= (p & -p)) {
      ret += a[p];
    }
    return ret;
  }
} bit;

std::vector<int> ver[N];

int dfn[N], tot;
int dep[N], siz[N], hson[N], fa[N];

int f[N][17];

void dfs(const int u) {
  dfn[u] = ++tot;
  for (int i = 1; i < 17; ++i) {
    f[u][i] = f[f[u][i - 1]][i - 1];
  }
  siz[u] = 1;
  for (auto &&v: ver[u]) {
    if (v == fa[u]) {
      continue;
    }
    dep[v] = dep[u] + 1;
    fa[v] = u;
    f[v][0] = u;
    dfs(v);
    siz[u] += siz[v];
  }
}

int getLca(int u, int v) {
  if (dep[u] > dep[v]) {
    std::swap(u, v);
  }
  for (int i = 16; i >= 0; --i) {
    if (dep[f[v][i]] >= dep[u]) {
      v = f[v][i];
    }
  }
  if (u == v) {
    return u;
  }
  for (int i = 16; i >= 0; --i) {
    if (f[u][i] == f[v][i]) {
      u = f[u][i], v = f[v][i];
    }
  }
  return f[u][0];
}

int getPos(int u, int v) {
  for (int i = 16; i >= 0; --i) {
    if (dep[f[u][i]] > dep[v]) {
      u = f[u][i];
    }
  }
  return u;
}

int query(int p) {
  return bit.ask(dfn[p] + siz[p] - 1) - bit.ask(dfn[p] - 1);
}

int main() {
  std::cin.tie(0)->sync_with_stdio(false);
  std::cin >> n >> q;
  for (int i = 1; i < n; ++i) {
    int u, v;
    std::cin >> u >> v;
    ver[u].emplace_back(v);
    ver[v].emplace_back(u);
  }
  dfs(1);
  while (q--) {
    int k;
    std::cin >> k;
    std::vector<int> a(k);
    for (auto &ai: a) {
      std::cin >> ai;
    }
    if (k == 1) {
      std::cout << "Yes\n";
      continue;
    }
    std::vector<std::pair<int,int>> roll_back(k - 1);
    bool flag = false;
    for (size_t i = 0; i + 1 < k; ++i) {
      int lca = getLca(a[i], a[i + 1]);
      int pos = getPos(a[i], lca);
      bit.insert(pos, dep[a[i]] - dep[lca]);
      roll_back[i] = {pos, dep[a[i]] - dep[lca]};
      int qwq = query(pos);
      if (qwq == siz[pos]) {
        flag = true;
        break;
      }
    }
    if (flag) {
      std::cout << "No\n";
    } else {
      std::cout << "Yes\n";
    }
    for (auto &&[p, k] : roll_back) {
      bit.insert(p, -k);
    }
  }
  return 0;
}

詳細信息

Test #1:

score: 0
Runtime Error

input:

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

output:


result: