QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#113034 | #4814. Exciting Travel | nhuang685 | WA | 1ms | 3580kb | C++20 | 9.1kb | 2023-06-16 01:50:08 | 2023-06-16 01:50:11 |
Judging History
answer
/**
* @file qoj4814F1.cpp
* @author nhuang685
* @brief
* @date 2023-06-15
*
*
*/
#include <bits/stdc++.h>
#ifdef LOCAL
std::ifstream cin;
std::ofstream cout;
using std::cerr;
#else
using std::cin;
using std::cout;
#define cerr \
if (false) std::cerr
#endif
template <class T>
class RSegB {
protected:
int sz;
std::vector<T> val;
virtual void push(int ind, int l, int r) = 0;
virtual void initLazy() = 0;
void pull(int ind) { val[ind] = comb(val[2 * ind], val[2 * ind + 1]); }
template <class F>
void modify(int a, int b, const T &v, const F &addToLazy, int ind, int l,
int r) {
push(ind, l, r);
if (a <= l && r <= b) {
addToLazy(ind, v);
push(ind, l, r);
return;
} else if (b < l || r < a)
return;
int mid = (l + r) / 2;
modify(a, b, v, addToLazy, 2 * ind, l, mid);
modify(a, b, v, addToLazy, 2 * ind + 1, mid + 1, r);
pull(ind);
}
T query(int a, int b, int ind, int l, int r) {
push(ind, l, r);
if (a <= l && r <= b)
return val[ind];
else if (b < l || r < a)
return ID();
int mid = (l + r) / 2;
return comb(query(a, b, 2 * ind, l, mid),
query(a, b, 2 * ind + 1, mid + 1, r));
}
public:
virtual T ID() = 0;
virtual T comb(const T &a, const T &b) = 0;
void init(int _sz) {
sz = 1;
while (sz < _sz) sz *= 2;
val.resize(2 * sz, ID());
initLazy();
}
void init(const std::vector<T> &arr) {
init((int)arr.size());
for (int i = 0; i < (int)arr.size(); ++i) {
val[i + sz] = arr[i];
}
for (int i = sz - 1; i >= 1; --i) pull(i);
}
T query(int a, int b) { return query(a, b, 1, 0, sz - 1); }
};
template <class T>
class LSeg : public RSegB<T> {
private:
std::vector<T> ls;
void push(int ind, int l, int r) {
if (ls[ind] == ID2()) return;
RSegB<T>::val[ind] = (r - l + 1) * ls[ind];
if (l != r) {
ls[2 * ind] = ls[ind];
ls[2 * ind + 1] = ls[ind];
}
ls[ind] = ID2();
}
void initLazy() { ls.resize(2 * RSegB<T>::sz, ID2()); }
public:
T ID() { return 0; }
T ID2() { return -1; } // change ID2 if necessary
T comb(const T &a, const T &b) { return a + b; }
void set(int a, int b, T v) {
RSegB<T>::modify(
a, b, v, [this](int ind, const T &value) { ls[ind] = value; }, 1, 0,
RSegB<T>::sz - 1);
}
void set(int i, T v) { set(i, i, v); }
};
template <class T, class RangeQ>
class HLDB {
// code based on https://codeforces.com/blog/entry/22072
protected:
int N;
std::vector<int> p, r, h, d, ind;
RangeQ seg;
bool edge;
int init(int node, const std::vector<std::vector<int>> &adj) {
int heavySz = -1, sz = 1;
for (int i : adj[node]) {
if (i == p[node]) continue;
p[i] = node;
d[i] = d[node] + 1;
int cSz = init(i, adj);
sz += cSz;
if (cSz > heavySz) {
heavySz = cSz;
h[node] = i;
}
}
return sz;
}
template <class F>
void upd(int i, const F &f) {
f(ind[i]);
}
template <class F>
void upd(int u, int v, const F &f) {
for (; r[u] != r[v]; v = p[r[v]]) {
if (d[r[u]] > d[r[v]]) std::swap(u, v);
f(ind[r[v]], ind[v]);
}
if (d[u] > d[v]) std::swap(u, v);
f(ind[u], ind[v]);
}
public:
void init(const std::vector<std::vector<int>> &adj) {
N = static_cast<int>(adj.size());
p.assign(N, -1);
h.assign(N, -1);
d.assign(N, 0);
init(0, adj);
r.assign(N, -1);
ind.assign(N, 0);
int cnt = 0;
for (int i = 0; i < N; ++i)
if (p[i] == -1 || h[p[i]] != i)
for (int j = i; j != -1; j = h[j]) {
r[j] = i;
ind[j] = cnt++;
}
seg.init(N);
}
T query(int i, int j) {
T res = seg.ID();
upd(i, j,
[this, &res](int u, int v) { res = seg.comb(res, seg.query(u, v)); });
return res;
}
int lca(int u, int v) {
for (; r[u] != r[v]; v = p[r[v]]) {
if (d[r[u]] > d[r[v]]) std::swap(u, v);
}
if (d[u] > d[v]) std::swap(u, v);
return u;
}
};
template <class T>
class SegB {
protected:
int sz;
std::vector<T> val;
virtual T ID() = 0;
virtual T comb(const T &a, const T &b) = 0;
void pull(int ind) { val[ind] = comb(val[2 * ind], val[2 * ind + 1]); }
template <class F>
void upd(int i, const T &a, const F &add) {
add(i += sz, a);
for (i /= 2; i >= 1; i /= 2) pull(i);
}
public:
void init(int _sz) {
sz = 1;
while (sz < _sz) sz *= 2;
val.assign(2 * sz, ID());
}
void init(const std::vector<T> &arr) {
init(static_cast<int>(arr.size()));
for (int i = 0; i < static_cast<int>(arr.size()); ++i) {
val[i + sz] = arr[i];
}
for (int i = sz - 1; i >= 1; --i) pull(i);
}
void set(int i, const T &a) {
upd(i, a, [this](int ind, const T &v) { val[ind] = v; });
}
T query(int i, int j) {
T l = ID(), r = ID();
for (i += sz, j += sz; i <= j; i /= 2, j /= 2) {
if (i % 2 == 1) l = comb(val[i++], l);
if (j % 2 == 0) r = comb(r, val[j--]);
}
return comb(l, r);
}
};
template <class T>
class HLD : public HLDB<T, LSeg<T>> {
using B = HLDB<T, LSeg<T>>;
public:
void set(int i, const T &v) {
B::upd(i, [this, &v](int u) { B::seg.set(u, v); });
}
void set(int a, int b, const T &v) {
B::upd(a, b, [this, &v](int u, int j) { B::seg.set(u, j, v); });
}
};
class Tour {
private:
template <class T>
class Seg : public SegB<T> {
public:
constexpr static T id = {(int)1e9, (int)1e9};
T ID() { return id; }
T comb(const T &a, const T &b) { return std::min(a, b); }
void add(int i, const T &a) {
SegB<T>::upd(i, a,
[this](int ind, const T &v) { SegB<T>::val[ind] += v; });
}
};
std::vector<int> ind, d;
int sz;
Seg<std::pair<int, int>> seg;
void dfs(int node, int par, const std::vector<std::vector<int>> &adj,
std::vector<std::pair<int, int>> &t) {
ind[node] = (int)t.size();
t.emplace_back(d[node], node);
for (int i : adj[node]) {
if (i == par) continue;
d[i] = d[node] + 1;
dfs(i, node, adj, t);
t.emplace_back(d[node], node);
}
}
public:
Tour(const std::vector<std::vector<int>> &adj) {
sz = (int)adj.size();
std::vector<std::pair<int, int>> t;
ind.resize(sz);
d.resize(sz);
dfs(0, -1, adj, t);
seg.init(t);
}
int lca(int u, int v) {
return seg.query(std::min(ind[u], ind[v]), std::max(ind[u], ind[v])).second;
}
const int &operator[](int i) { return ind[i]; }
int depth(int i) { return d[i]; }
int size() { return sz; }
};
class VT {
private:
Tour &t;
int sz, cnt = 0;
std::vector<int> ind;
std::vector<std::vector<int>> vtadj;
std::vector<int> p;
public:
VT(Tour &_t) : t(_t), sz(_t.size()), ind(_t.size()) {}
void init(std::vector<int> v) {
v.push_back(0);
std::sort(v.begin(), v.end(), [this](int a, int b) { return t[a] < t[b]; });
v.erase(std::unique(v.begin(), v.end()), v.end());
int vsz = (int)v.size();
for (int i = 0; i < vsz - 1; ++i) v.push_back(t.lca(v[i], v[i + 1]));
std::sort(v.begin(), v.end(), [this](int a, int b) { return t[a] < t[b]; });
v.erase(std::unique(v.begin(), v.end()), v.end());
for (cnt = 0; cnt < (int)v.size(); ++cnt) ind[v[cnt]] = cnt;
vtadj.resize(cnt);
p.resize(cnt);
std::stack<int> s;
for (int node : v) {
if (!vtadj[ind[node]].empty()) vtadj[ind[node]].clear();
if (node == 0) {
s.push(0);
continue;
}
int par = t.lca(s.top(), node);
while (!s.empty() && t.depth(par) <= t.depth(s.top())) s.pop();
if (t.depth(par) < t.depth(node)) {
vtadj[ind[par]].push_back(ind[node]);
vtadj[ind[node]].push_back(ind[par]);
p[ind[node]] = ind[par];
}
s.push(node);
}
}
const auto &operator[](int node) { return ind[node]; }
const auto &adj(int node) { return vtadj[ind[node]]; }
const auto &adj() { return vtadj; }
int par(int i) { return p[ind[i]]; }
};
int main() {
#ifdef LOCAL
cin.open("input.txt");
cout.rdbuf()->pubsetbuf(0, 0);
cout.open("output.txt");
#else
cin.tie(nullptr)->sync_with_stdio(false);
#endif
int n, m;
cin >> n >> m;
std::vector<std::vector<int>> adj(n);
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
x--, y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
Tour t(adj);
VT vt(t);
while (m--) {
int k;
cin >> k;
std::vector<int> x(k);
for (int i = 0; i < k; ++i) cin >> x[i], x[i]--;
vt.init(x);
HLD<int> im;
HLD<int> v;
int ans = 0;
im.init(vt.adj());
v.init(vt.adj());
for (int i : x) im.set(vt[i], 1);
for (int i = 0; i < k - 1; ++i) {
int a = vt[x[i]], b = vt[x[i + 1]];
if (im.query(a, b) > 2 || v.query(a, b) > 1) {
ans++;
v.set(a, 1);
v.set(b, 1);
} else
v.set(a, b, 1);
}
cout << ans << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3444kb
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: 1ms
memory: 3464kb
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: 1ms
memory: 3580kb
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: 3484kb
input:
1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3472kb
input:
1 0
output:
result:
ok 0 number(s): ""
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3520kb
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 3 0 0 4 0 0 0 4 4
result:
wrong answer 7th numbers differ - expected: '2', found: '3'