QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#85597 | #4814. Exciting Travel | Scintilla | WA | 10ms | 18764kb | C++14 | 4.1kb | 2023-03-07 22:00:48 | 2023-03-07 22:00:52 |
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 (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: 10ms
memory: 17996kb
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: -100
Wrong Answer
time: 4ms
memory: 18764kb
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 2 4 3 5
result:
wrong answer 4th numbers differ - expected: '1', found: '2'