QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#85600#4814. Exciting TravelScintillaWA 8ms19900kbC++144.1kb2023-03-07 22:04:412023-03-07 22:04:42

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:04:42]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:19900kb
  • [2023-03-07 22:04:41]
  • 提交

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 (val == 1 && 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: 3ms
memory: 18272kb

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: 5ms
memory: 19260kb

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: 5ms
memory: 19760kb

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: 18420kb

input:

1 1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 8ms
memory: 18080kb

input:

1 0

output:


result:

ok 0 number(s): ""

Test #6:

score: 0
Accepted
time: 3ms
memory: 18472kb

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
2
0
0
4
0
0
0
4
4

result:

ok 15 numbers

Test #7:

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

input:

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

output:

0
3
1
3
0
0
0
0
0
0
0
5
6
1
6

result:

ok 15 numbers

Test #8:

score: 0
Accepted
time: 3ms
memory: 19484kb

input:

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

output:

1
1
0
2
6
3
0
0
0
0
7
0
0
5
0

result:

ok 15 numbers

Test #9:

score: -100
Wrong Answer
time: 8ms
memory: 18672kb

input:

1000 500
685 415
28 527
771 396
201 538
604 162
631 66
144 596
788 378
919 59
737 550
471 413
3 590
891 52
886 705
350 238
164 224
554 358
909 150
354 441
310 756
380 661
380 867
601 318
197 204
993 673
118 624
249 539
841 737
742 853
250 566
543 663
981 243
60 120
976 801
750 2
694 8
935 831
381 48...

output:

0
3
0
3
4
2
2
0
2
0
4
0
1
4
5
2
0
12
0
14
3
3
5
3
0
0
2
0
4
9
5
5
1
0
40
12
0
18
4
1
1
6
0
7
3
0
0
14
5
1
3
8
5
0
4
0
5
7
2
5
6
0
5
0
1
2
7
3
0
0
6
0
1
8
4
1
11
0
1
0
8
3
2
0
1
2
0
3
9
5
13
2
0
4
2
0
4
1
14
1
4
4
4
0
1
1
10
2
2
0
0
4
10
2
3
10
4
0
13
6
0
19
3
4
9
2
10
6
1
0
0
3
0
0
5
12
5
2
2
1
9
15...

result:

wrong answer 135th numbers differ - expected: '6', found: '5'