QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#85601 | #4814. Exciting Travel | Scintilla | WA | 12ms | 19952kb | C++14 | 4.2kb | 2023-03-07 22:07:03 | 2023-03-07 22:07:05 |
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];
} ;
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 18668kb
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: 2ms
memory: 19176kb
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: 18224kb
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: 19540kb
input:
1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 6ms
memory: 18024kb
input:
1 0
output:
result:
ok 0 number(s): ""
Test #6:
score: 0
Accepted
time: 4ms
memory: 18512kb
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: 18068kb
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: 4ms
memory: 19952kb
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: 12ms
memory: 18156kb
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'