QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#64846 | #4814. Exciting Travel | ckiseki# | WA | 4ms | 9604kb | C++17 | 7.8kb | 2022-11-25 19:10:50 | 2022-11-25 19:10:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
static constexpr int maxn = 2'000'00 + 5;
static constexpr int kLog = 19;
static constexpr inline int lowbit(int x) { return x & (-x); }
class LBD {
int tc, chains;
vector<vector<int>> G;
vector<int> tl, tr, chain, head, dep, pa;
void predfs(int u, int f) {
dep[u] = dep[pa[u] = f] + 1;
for (int v : G[u]) if (v != f) {
predfs(v, u);
if (lowbit(chain[u]) < lowbit(chain[v]))
chain[u] = chain[v];
}
if (chain[u] == 0) chain[u] = ++chains;
}
void dfschain(int u, int f) {
tl[u] = tc++;
if (head[chain[u]] == -1)
head[chain[u]] = u;
for (int v : G[u])
if (v != f and chain[v] == chain[u])
dfschain(v, u);
for (int v : G[u])
if (v != f and chain[v] != chain[u])
dfschain(v, u);
tr[u] = tc;
}
public:
LBD(int n) : tc(0), chains(0), G(n), tl(n), tr(n), chain(n), head(n, -1), dep(n), pa(n) {}
void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
void decompose() {
predfs(0, 0);
dfschain(0, 0);
}
pair<int, int> get_subtree(int u) const {
return {tl[u], tr[u]};
}
vector<pair<int, int>> get_path(int u, int v) {
vector<pair<int, int>> res;
while (chain[u] != chain[v]) {
if (dep[head[chain[u]]] < dep[head[chain[v]]])
swap(u, v);
int s = head[chain[u]];
res.emplace_back(tl[s], tl[u] + 1);
u = pa[s];
}
if (dep[u] < dep[v]) swap(u, v);
res.emplace_back(tl[v], tl[u] + 1);
return res;
}
};
class BIT {
vector<int> b;
int query(int p) {
int r = 0;
while (p) {
r += b[p];
p -= lowbit(p);
}
return r;
}
public:
BIT(int n) : b(n) {}
void add(int p, int x) {
while (p < int(b.size())) {
b[p] += x;
p += lowbit(p);
}
}
int query(int l, int r) {
// cerr << "> query(" << l << ", " << r << "] @ " << b.size() << endl;
return query(r) - query(l);
}
};
class DS : public LBD {
BIT bit;
public:
DS(int n) : LBD(n), bit(n + 1) {}
// void add_edge(int, int);
// void decompose();
void add(int u, int x) {
auto [p, _] = get_subtree(u);
bit.add(p + 1, x);
}
int query(int u, int v) {
int s = 0;
for (auto [l, r] : get_path(u, v))
s += bit.query(l, r);
return s;
}
};
int pa[maxn][kLog];
vector<int> g[maxn];
int tin[maxn], tout[maxn], tc;
bool anc(int u, int v) {
return tin[u] <= tin[v] and tout[v] <= tout[u];
}
int lca(int u, int v) {
if (anc(u, v)) return u;
for (int i = kLog - 1; i >= 0; --i)
if (not anc(pa[u][i], v))
u = pa[u][i];
return pa[u][0];
}
void dfs(int u, int f) {
pa[u][0] = f;
for (int i = 1; i < kLog; ++i)
pa[u][i] = pa[pa[u][i - 1]][i - 1];
tin[u] = tc++;
for (int v : g[u]) {
if (v == f) continue;
dfs(v, u);
}
tout[u] = tc;
}
vector<pair<int, int>> get_tree(vector<int> vs, int r = 0) {
vector<pair<int, int>> res;
sort(vs.begin(), vs.end(), [](int i, int j) {
return tin[i] < tin[j];
});
vs.erase(unique(vs.begin(), vs.end()), vs.end());
vector<int> s = {r};
for (int v : vs) if (v != r) {
if (int o = lca(v, s.back()); o != s.back()) {
while (s.size() >= 2) {
if (tin[s[s.size() - 2]] < tin[o])
break;
res.emplace_back(s[s.size() - 2], s.back());
s.pop_back();
}
if (s.back() != o) {
res.emplace_back(o, s.back());
s.back() = o;
}
}
s.push_back(v);
}
for (size_t i = 1; i < s.size(); ++i)
res.emplace_back(s[i - 1], s[i]);
return res;
}
pair<int, int> shrink(int u, int v) {
if (u == v) {
return {-1, -1};
}
#define chk() if (anc(u, v)) {\
if (pa[v][0] == u) \
return {-1, -1}; \
int o = pa[v][0];\
for (int i = kLog - 1; i >= 0; --i) \
if (not anc(pa[v][i], u)) v = pa[v][i]; \
return {o, v}; \
}
chk();
swap(u, v);
chk();
return {pa[v][0], pa[u][0]};
}
int main() {
#ifdef CKISEKI
freopen("e.3.in", "r", stdin);
#endif
cin.tie(nullptr)->sync_with_stdio(false);
int N, Q; cin >> N >> Q;
DS allds(N);
for (int i = 1; i < N; ++i) {
int u, v; cin >> u >> v;
--u, --v;
allds.add_edge(u, v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(0, 0);
allds.decompose();
vector<vector<int>> vt(N);
vector<int> ID(N, -1);
// for (int i = 0; i < Q; i++) {
while (Q--) {
int k;
cin >> k;
if (k == 1) {
cout << "0\n";
continue;
}
vector<int> x(k);
for (int j = 0; j < k; j++) {
cin >> x[j];
--x[j];
allds.add(x[j], 1);
}
int adj = 0;
vector<pair<int,int>> path(k);
vector<int> vtx = x;
for (int j = 1; j < k; j++) {
path[j] = shrink(x[j-1], x[j]);
auto &[a, b] = path[j];
// cerr << "x[j-1], x[j] = " << x[j-1] << ", " << x[j] << endl;
// cerr << "a, b = " << a << ", " << b << endl;
if (a == -1) {
// adjacent
// cerr << "ADJ " << a << ", " << b << endl;
++adj;
continue;
}
if (allds.query(a, b) != 0) {
// cerr << "HAS VTX " << a << ", " << b << endl;
// yang
a = b = -1;
continue;
}
vtx.emplace_back(a);
vtx.emplace_back(b);
}
const auto vt_edges = get_tree(vtx);
for (const auto [u, v]: vt_edges)
ID[u] = ID[v] = -1;
int curID = 0;
for (const auto [u, v]: vt_edges) {
if (ID[u] == -1) ID[u] = curID++;
if (ID[v] == -1) ID[v] = curID++;
}
// cerr << "curID = " << curID << endl;
DS ds(curID);
for (const auto [u, v]: vt_edges) {
// cerr << ID[u] << "(" << u+1 << ")"
// << " -> " << ID[v] << "(" << v+1 << ")" << endl;
ds.add_edge(ID[u], ID[v]);
vt[ID[u]].emplace_back(ID[v]);
}
ds.decompose();
// cerr << "-----\n";
// cerr << "ID[0] = " << ID[0] << endl;
vector<vector<pair<int,int>>> paths(curID);
for (int j = 1; j < k; j++) {
auto [a, b] = path[j];
if (a == -1) continue;
int c = lca(a, b);
// cerr << "PATH " << ID[c] << ' ' << ID[a] << ' ' << ID[b] << endl;
paths[ID[c]].emplace_back( ID[a], ID[b] );
}
vector<int> dp(curID);
const auto dfs_vt = [&](auto self, int i) -> void {
int sum = 0;
for (int j: vt[i]) {
self(self, j);
}
for (int j: vt[i])
sum += dp[j];
dp[i] = sum;
for (auto [a, b]: paths[i]) {
dp[i] = max(dp[i], ds.query(a, b) + 1);
}
ds.add(i, sum);
// cerr << "i, dp[i] = " << i+1 << ' ' << dp[i] << endl;
};
// cerr << "ID[root] = " << ID[0] << endl;
dfs_vt(dfs_vt, ID[0]);
int ans = *max_element(dp.begin(), dp.end());
cout << k - 1 - ans - adj << '\n';
for (int j = 0; j < k; j++) {
allds.add(x[j], -1);
}
for (const auto [u, v]: vt_edges) {
// paths[ID[u]].clear();
// paths[ID[v]].clear();
vt[ID[u]].clear();
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 9604kb
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: 3ms
memory: 8452kb
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 2 2 0 2 0 0
result:
wrong answer 2nd numbers differ - expected: '0', found: '2'