QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#85600 | #4814. Exciting Travel | Scintilla | WA | 8ms | 19900kb | C++14 | 4.1kb | 2023-03-07 22:04:41 | 2023-03-07 22:04:42 |
Judging History
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'