QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#85582 | #4814. Exciting Travel | Scintilla | WA | 1ms | 19228kb | C++14 | 4.0kb | 2023-03-07 21:35:44 | 2023-03-07 21:35:46 |
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;
} ;
rep(i, 2, k) {
while (top > 1 && dep[LCA(cs[i], st[top])] < dep[st[top]]) pop();
if (LCA(cs[i], st[top]) != st[top]) st[++ top] = LCA(cs[i], st[top]);
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]);
auto upd = [&](int x, int y, int val) {
// cout << "u, x, y = " << u << ' ' << x << ' ' << y << endl;
if (pre[x] - pre[u] > 1 || pre[y] - pre[u] > 1) return;
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);
// pv(w);
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;
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: 0
Wrong Answer
time: 1ms
memory: 19228kb
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 3
result:
wrong answer 3rd numbers differ - expected: '2', found: '3'