QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#85597#4814. Exciting TravelScintillaWA 10ms18764kbC++144.1kb2023-03-07 22:00:482023-03-07 22:00:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-07 22:00:52]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:18764kb
  • [2023-03-07 22:00:48]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb emplace_back
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

using pii = pair <int, int>;

const int INF = 0x3f3f3f3f;

const int N = 2e5 + 10;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

void cmax(int &a, int b) { a < b ? a = b : 1; }
void cmin(int &a, int b) { a > b ? a = b : 1; }

int n, m, p[N], dep[N], dfn[N], dn, sz[N], tb[N][20];
vector <int> e[N];

int Min(int u, int v) {
  return dep[u] < dep[v] ? u : v;
}

void dfs0(int u, int fa) {
  p[u] = fa, dfn[u] = ++ dn, tb[dfn[u]][0] = u, sz[u] = 1;
  for (int v : e[u]) if (v != fa) dep[v] = dep[u] + 1, dfs0(v, u), sz[u] += sz[v];
}

int LCA(int u, int v) {
  if (u == v) return u;
  u = dfn[u], v = dfn[v];
  if (u > v) swap(u, v);
  int t = __lg(v - u ++);
  return p[Min(tb[u][t], tb[v - (1 << t) + 1][t])];
}

int len, s[N], cs[N], top, st[N], cnt, o[N], id[N], f[N][2], sum[N], pre[N];
vector <int> g[N];
vector <pii> path[N];

void build() {
  int k = len;
  rep(i, 1, k) cs[i] = s[i];
  if (!count(cs + 1, cs + k + 1, 1)) cs[++ k] = 1;
  sort(cs + 1, cs + k + 1, [&](int u, int v) {
    return dfn[u] < dfn[v];
  });
  st[top = 1] = o[cnt = 1] = 1;
  auto pop = [&]() {
    o[++ cnt] = st[top], g[st[top - 1]].pb(st[top]), -- top;
  } ;
  for (int i = 2, lca; lca = 0, i <= k; ++ i) {
    while (dep[LCA(cs[i], st[top])] < dep[st[top]]) lca = LCA(cs[i], st[top]), pop();
    if (lca && lca != st[top]) st[++ top] = lca;
    st[++ top] = cs[i];
  }
  while (top > 1) pop();
}

namespace bit {

  int c[N];
  void add(int u, int k) { for (; u < N; u += u & -u) c[u] += k; }
  int ask(int u) { int res = 0; for (; u; u -= u & -u) res += c[u]; return res; }
  void add(int l, int r, int k) { add(l, k), add(r + 1, -k); }

}

using bit::add;
using bit::ask;

void clr() {
  for (; cnt; -- cnt) {
    int u = o[cnt];
    g[u].clear(), path[u].clear(), id[u] = 0;
    add(dfn[u], dfn[u] + sz[u] - 1, max(f[u][0], f[u][1]) - sum[u]);
  }
}

void dfs(int u) {
  // cout << "----- dfs u = " << u << endl;
  f[u][0] = f[u][1] = sum[u] = 0, pre[u] += !!id[u];
  for (int v : g[u]) pre[v] = pre[u], dfs(v), sum[u] += max(f[v][0], f[v][1]);
  f[u][1] = sum[u];
  auto upd = [&](int x, int y, int val) {
    if (pre[x] - pre[u] > 1 || pre[y] - pre[u] > 1) return;
    if (x != u && y != u && id[u]) return;
    // cout << "u, x, y = " << u << ' ' << x << ' ' << y << endl;
    int w = val + sum[u] + ask(dfn[x]) + ask(dfn[y]);
    // pv(w);
    if (x != u) w += max(f[x][1] - sum[x], 0);
    if (y != u) w += max(f[y][1] - sum[y], 0);
    cmax(f[u][x == u || y == u], w);
    // cout << "u, x, y, w = " << u << ' ' << x << ' ' << y << ' ' << w << endl;
    // pa(f[u], 0, 1);
  } ;
  for (auto [x, y] : path[u]) upd(x, y, 1);
  auto in = [&](int x, int y) {
    return dfn[x] < dfn[y] && dfn[y] < dfn[x] + sz[x];
  } ;
  int x = s[id[u] - 1], y = s[id[u] + 1];
  if (x && y && in(u, x) && in(u, y)) upd(x, y, 2);
  add(dfn[u], dfn[u] + sz[u] - 1, sum[u] - max(f[u][0], f[u][1]));
}

void solve() {
  len = read(), s[len + 1] = 0, pre[1] = 0;
  rep(i, 1, len) {
    s[i] = read(), id[s[i]] = i;
    if (i > 1) path[LCA(s[i - 1], s[i])].pb(mp(s[i - 1], s[i]));
  }
  build();
  // pa(o, 1, cnt);
  dfs(1);
  // rep(i, 1, n) {
    // pa(f[i], 0, 1);
  // }
  printf("%d\n", len - 1 - max(f[1][0], f[1][1]));
  clr();
}

int main() {
  n = read(), m = read();
  rep(i, 1, n - 1) {
    int u = read(), v = read();
    e[u].pb(v), e[v].pb(u);
  }
  dfs0(1, 0);
  rep(j, 1, 19) rep(i, 1, n - (1 << j) + 1) {
    tb[i][j] = Min(tb[i][j - 1], tb[i + (1 << j - 1)][j - 1]);
  }
  while (m --) solve();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 17996kb

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

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
2
4
3
5

result:

wrong answer 4th numbers differ - expected: '1', found: '2'