이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ar array
using namespace std;
template<class S, class F>
struct SegTreeBase {
vector<S> values;
vector<F> queued;
int lg2, offset;
static constexpr int log2i(unsigned n) { return 32-__builtin_clz(--n); }
SegTreeBase(const vector<S> &src)
: lg2(log2i((int)src.size())), offset(1<<log2i((int)src.size())) {
values.reserve(2*offset);
values.resize(offset);
values.insert(values.end(), src.begin(), src.end());
values.resize(2*offset);
queued.resize(offset);
for (int i = offset-1; i > 0; --i) recalc(i);
}
void recalc(int I) {
assert(I > 0 && I < offset);
values[I] = values[2*I] * values[2*I+1];
}
void push(int I) {
assert(I > 0 && I < offset);
values[2*I] = queued[I] * values[2*I];
values[2*I+1] = queued[I] * values[2*I+1];
if (2*I < offset) {
queued[2*I] = queued[I] * queued[2*I];
queued[2*I+1] = queued[I] * queued[2*I+1];
}
queued[I] = F();
}
void push_col(int I) {
assert(I >= offset && I < 2*offset);
for (int lvl = lg2-1; lvl >= 0; --lvl)
push((I>>lvl)/2);
}
void push_range(int I, int J) {
assert(I+1 >= offset && I+1 < 2*offset);
assert(J-1 >= offset && J-1 < 2*offset);
assert(I+1 < J);
for (int lvl = lg2-1; lvl >= 0; --lvl) {
push(((I+1)>>lvl)/2);
if (I+1 != J-1) push(((J-1)>>lvl)/2);
}
}
void set(int i, S v) {
assert(i >= 0 && i < offset);
i += offset;
push_col(i);
values[i] = v;
while (i /= 2) recalc(i);
}
void upd_node(int I, const F &f) {
assert(I > 0 && I < 2*offset);
values[I] = f * values[I];
if (I < offset) queued[I] = f * queued[I];
}
void upd(int i, const F &f) {
assert(i >= 0 && i < offset);
i += offset;
push_col(i);
upd_node(i, f);
while (i/=2) recalc(i);
}
void upd(int i, int j, const F &f) {
assert(i >= 0 && i < offset);
assert(j >= 0 && j < offset);
assert(i <= j);
i += offset-1;
j += offset+1;
int oi = i, oj = j;
push_range(i, j);
while (i+1 < j) {
if ((i&1)==0) upd_node(i+1, f);
if ((j&1)==1) upd_node(j-1, f);
i >>= 1, j >>= 1;
}
i = oi+1, j = oj-1;
for (int lvl = 1; lvl <= lg2; lvl++) {
if (__builtin_ctz(i) < lvl) recalc(i >> lvl);
if (__builtin_ctz(j+1) < lvl) recalc(j >> lvl);
}
}
S qry(int i) {
assert(i >= 0 && i < offset);
i += offset;
push_col(i);
return values[i];
}
S qry(int i, int j) {
assert(i >= 0 && i < offset);
assert(j >= 0 && j < offset);
assert(i <= j);
i += offset-1;
j += offset+1;
push_range(i, j);
S ls, rs;
while (i+1 < j) {
if ((i&1)==0) ls = ls * values[i+1];
if ((j&1)==1) rs = values[j-1] * rs;
i >>= 1, j >>= 1;
}
return ls * rs;
}
template<class Cmp>
int upper_bound(S t, Cmp cmp) {
if (cmp(values[1], t)) return offset;
int lvl = lg2;
int I = 1;
S pre;
while (lvl--) {
I *= 2;
push(I/2);
if (cmp(pre*values[I], t)) {
pre = pre*values[I];
++I;
}
}
return I - offset;
}
};
struct SumS {
int w = 1;
int s = 0;
SumS operator*(const SumS &rhs) const {
return {w+rhs.w, s+rhs.s};
}
};
struct SumF {
int sum = 0;
SumF operator*(const SumF &rhs) const {
return {rhs.sum+sum};
}
SumS operator*(const SumS &rhs) const {
return {rhs.w, rhs.s + sum * rhs.w};
}
};
struct TouchS {
bool v = false;
TouchS operator*(const TouchS &rhs) const {
return {bool(v | rhs.v)};
}
};
struct TouchF {
bool s0 = false;
bool s1 = false;
TouchF operator*(const TouchF &rhs) const {
if (s0) return {true, false};
if (s1) return {false, true};
return rhs;
}
TouchS operator*(const TouchS &rhs) const {
if (s0) return {false};
if (s1) return {true};
return rhs;
}
};
using SumST = SegTreeBase<SumS, SumF>;
using TouchST = SegTreeBase<TouchS, TouchF>;
const int mxN = 1e5;
vector<ar<int, 2>> g[mxN];
int sz[mxN];
int up_id[mxN];
int dof[mxN];
int up[20][mxN];
int dfs1(int cur, int prv, int d) {
sz[cur] = 1;
dof[cur] = d;
for (auto [nxt, nn] : g[cur]) {
if (nxt == prv) continue;
sz[cur] += dfs1(nxt, cur, d+1);
up_id[nxt] = nn;
up[0][nxt] = cur;
}
return sz[cur];
}
int order[mxN];
int pof[mxN];
int chain_top[mxN];
void dfs2(int &I, int cur, int prv, int ct) {
int heavy = -1;
int heavy_sz = 0;
order[I] = cur;
pof[cur] = I++;
chain_top[cur] = ct;
for (auto [nxt, nn] : g[cur]) {
if (nxt == prv) continue;
if (sz[nxt] <= heavy_sz) continue;
heavy = nxt;
heavy_sz = sz[nxt];
}
if (heavy != -1) dfs2(I, heavy, cur, ct);
for (auto [nxt, nn] : g[cur]) {
if (nxt == prv) continue;
if (nxt == heavy) continue;
dfs2(I, nxt, cur, nxt);
}
}
int lca(int i, int j) {
if (dof[i] > dof[j]) swap(i, j);
for (int lvl = 19; lvl >= 0; --lvl)
if (dof[up[lvl][j]] >= dof[i])
j = up[lvl][j];
assert(dof[i] == dof[j]);
if (i == j) return i;
for (int lvl = 19; lvl >= 0; --lvl)
if (up[lvl][i] != up[lvl][j])
i = up[lvl][i], j = up[lvl][j];
assert(i != j);
i = up[0][i], j = up[0][j];
assert(i == j);
return i;
}
SumST *sum_st;
TouchST *touch_st;
int find_hi(int i, int j) {
//cerr << "find_hi: " << i << ' ' << j << ' ';
//assert(lca(i, j)==j);
for (int lvl = 19; lvl >= 0; --lvl) {
if (dof[up[lvl][i]] <= dof[j]) continue;
if (touch_st->qry(pof[up[lvl][i]]).v) continue;
i = up[lvl][i];
}
//cerr << i << '\n';
return up[0][i];
}
void add(int i, int j) {
//assert(lca(i, j)==j);
//cerr << "add " << i << ' ' << j << '\n';
while (chain_top[i] != chain_top[j]) {
sum_st->upd(pof[chain_top[i]], pof[i], {1});
i = up[0][chain_top[i]];
}
if (i != j)
sum_st->upd(pof[j]+1, pof[i], {1});
}
void touch(int i, int j) {
//assert(lca(i, j)==j);
//cerr << "touch " << i << ' ' << j << '\n';
while (chain_top[i] != chain_top[j]) {
touch_st->upd(pof[chain_top[i]], pof[i], {false, true});
i = up[0][chain_top[i]];
}
if (i != j)
touch_st->upd(pof[j]+1, pof[i], {false, true});
}
void untouch(int i, int j) {
//assert(lca(i, j)==j);
//cerr << "untouch " << i << ' ' << j << '\n';
while (chain_top[i] != chain_top[j]) {
touch_st->upd(pof[chain_top[i]], pof[i], {true, false});
i = up[0][chain_top[i]];
}
if (i != j)
touch_st->upd(pof[j]+1, pof[i], {true, false});
}
int main() {
int n, m, k; cin >> n >> m >> k;
for (int nn = 1; nn < n; ++nn) {
int i, j; cin >> i >> j; --i, --j;
//cerr << "edge: " << i << ' ' << j << '\n';
g[i].push_back({j, nn});
g[j].push_back({i, nn});
}
dfs1(0, -1, 0);
for (int lvl = 0; lvl < 19; ++lvl)
for (int i = 0; i < n; ++i)
up[lvl+1][i] = up[lvl][up[lvl][i]];
{
int I = 0;
dfs2(I, 0, -1, 0);
//assert(I==n);
}
/*
for (int i = 0; i < n; ++i)
cerr << chain_top[i] << " \n"[i==n-1];
for (int i = 0; i < n; ++i)
cerr << order[i] << " \n"[i==n-1]; // */
sum_st = new SumST(vector<SumS>(n, {1, 0}));
touch_st = new TouchST(vector<TouchS>(n, {false}));
int a[mxN];
for (int mm = 0; mm < m; ++mm) {
int s; cin >> s;
//cerr << s << ": ";
for (int ss = 0; ss < s; ++ss) {
cin >> a[ss], --a[ss];
//cerr << a[ss] << ' ';
}
int hi = a[0];
for (int ss = 1; ss < s; ++ss)
hi = lca(hi, a[ss]);
//cerr << "- " << hi << '\n';
for (int ss = 0; ss < s; ++ss) {
if (a[ss] == hi) continue;
add(a[ss], find_hi(a[ss], hi));
touch(a[ss], hi);
/*
cerr << "touched: ";
for (int i = 0; i < n; ++i)
cerr << touch_st->qry(i).v << " \n"[i==n-1]; // */
/*
cerr << "sum: ";
for (int i = 0; i < n; ++i)
cerr << sum_st->qry(i).s << " \n"[i==n-1]; */
}
for (int ss = 0; ss < s; ++ss) {
if (a[ss] == hi) continue;
untouch(a[ss], hi);
/*
cerr << "touched: ";
for (int i = 0; i < n; ++i)
cerr << touch_st->qry(i).v << " \n"[i==n-1]; // */
}
//cerr << '\n';
}
vector<int> ans;
for (int i = 0; i < n; ++i)
if (sum_st->qry(i).s >= k)
ans.push_back(up_id[order[i]]);
sort(ans.begin(), ans.end());
cout << ans.size() << '\n';
for (int mm : ans)
cout << mm << ' ';
cout << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |