이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define ld long double
#define ar array
const int INF = 1e17;
const int MOD = 1e9+7;
template<class T> struct SegmentTree {
int n; vector<T> values;
T IDENTITY = 0;
SegmentTree(int n, int id) : n(n), values(2*n, IDENTITY = id) {}
T calc_op(T a, T b) { return a + b; }
void modify(int i, T v) {
for (values[i += n] = v; i >>= 1; )
values[i] = calc_op(values[2*i], values[2*i + 1]);
}
T calc(int l, int r) {
T rans = IDENTITY, lans = IDENTITY;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) lans = calc_op(lans, values[l++]);
if (r & 1) rans = calc_op(values[--r], rans);
}
return calc_op(lans, rans);
}
};
const int MXN = 1e5+9;
vector<ar<int, 2>> g[MXN];
int N, M, K, up[20][MXN], depth[MXN], val[MXN];
int tin[MXN], tout[MXN], timer = 0;
vector<int> ans;
void dfs(int u, int pu) {
up[0][u] = pu; tin[u] = timer++;
for (int i = 1; i < 20; i++)
up[i][u] = up[i-1][up[i-1][u]];
for (auto v : g[u]) if (v[1] != pu) {
depth[v[1]] = depth[u] + 1;
dfs(v[1], u);
}
tout[u] = timer;
}
int lca(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
for (int i = 19; i >= 0; --i)
if ((depth[v] - depth[u]) >> i & 1)
v = up[i][v];
if (u == v) return u;
for (int i = 19; i >= 0; --i)
if (up[u][i] != up[v][i])
u = up[u][i], v = up[v][i];
return up[0][u];
}
void magic(int u, int pu) {
for (auto v : g[u]) if (v[1] != pu) {
magic(v[1], u);
if (val[v[1]] >= K) ans.push_back(v[0]);
val[u] += val[v[1]];
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N >> M >> K;
for (int i = 0; i < N - 1; ++i) {
int a, b; cin >> a >> b; --a, --b;
g[a].push_back({i, b}); g[b].push_back({i, a});
}
dfs(0, 0);
SegmentTree<int> seg(N, 0);
while (M--) {
int s; cin >> s;
vector<int> shit(s);
for (int &i : shit) cin >> i, --i;
sort(shit.begin(), shit.end(), [&](int i, int j) { return depth[i] > depth[j]; });
int baap = shit.back();
for (int i : shit) baap = lca(baap, i);
for (int i : shit) if (!seg.calc(tin[i], tout[i])) {
int x = i;
// get first top thingie with already +1 coz of this guy
for (int j = 19; j >= 0; --j)
if (depth[baap] < depth[up[j][x]] && !seg.calc(tin[up[j][x]], tout[up[j][x]]))
x = up[j][x];
x = up[0][x];
val[i]++; val[x]--;
seg.modify(tin[i], 1);
}
for (int i : shit) seg.modify(tin[i], 0);
}
magic(0, 0);
sort(ans.begin(), ans.end());
cout << ans.size() << '\n';
for (int i : ans) cout << i + 1 << ' ';
}
# | 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... |