QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#85602#4814. Exciting TravelScintillaWA 6ms19660kbC++144.2kb2023-03-07 22:08:182023-03-07 22:08:22

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:08:22]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:19660kb
  • [2023-03-07 22:08:18]
  • 提交

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][val == 2 || 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];
  } ;
  if (1 < id[u] && id[u] < len) {
    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;
}

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 19660kb

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

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: 6ms
memory: 17932kb

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: 3ms
memory: 17892kb

input:

1 1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #5:

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

input:

1 0

output:


result:

ok 0 number(s): ""

Test #6:

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

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: 3ms
memory: 17748kb

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: 2ms
memory: 17748kb

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: 4ms
memory: 18104kb

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'