| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 439667 | Ya_Ali | Railway (BOI17_railway) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* ** *** In the name of God *** ** */
// Only Haider is Amir al-Momenin
#include <bits/stdc++.H>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 10, lg = 17;
const ll mod = 1e9 + 7;
#define endl '\n'
ll tin [maxn], tout [maxn], anc [maxn][lg], H [maxn], khar_and_mother [maxn], tala [maxn], T, n, m, k;
vector <pair<ll, ll>> g [maxn];
vector <ll> A, ali;
void DFS (const ll &v = 1, const ll &pr = 1) {
tin[v] = ++T;
H[v] = H[pr] + 1;
anc[v][0] = pr;
for (ll i = 1; i < lg; i++) anc[v][i] = anc[anc[v][i - 1]][i - 1];
for (auto &u : g[v]) if (u.first != pr) DFS(u.first, v);
tout[v] = T;
}
inline ll up (ll v, const ll &d) { for (ll i = lg; i--;) if (d >> i & 1) v = anc[v][i]; return v; }
inline ll lca (ll v, ll u) {
if (H[v] > H[u]) swap(v, u);
u = up(u, H[u] - H[v]);
if (v == u) return v;
for (ll i = lg; i--;) if (anc[v][i] ^ anc[u][i]) v = anc[v][i], u = anc[u][i];
return anc[v][0];
}
void add (ll s) {
sort(A.begin(), A.end(), [&](const ll &v, const ll &u) { return tin[v] < tin[u]; });
for (ll i = 1; i < s; i++) A.push_back(lca(A[i - 1], A[i]));
sort(A.begin(), A.end(), [&](const ll &v, const ll &u) { return tin[v] < tin[u]; });
A.resize(unique(A.begin(), A.end()) - A.begin());
ali.clear();
for (auto &v : A) {
while (!ali.empty() && !(tin[ali.back()] <= tin[v] && tout[v] <= tout[ali.back()])) ali.pop_back();
if (!ali.empty()) khar_and_mother[v] = ali.back();
else khar_and_mother[v] = -1;
ali.push_back(v);
}
for (auto &v : A) if (khar_and_mother[v] != -1) tala[v]++, tala[khar_and_mother[v]]--;
}
ll what_the_fuck (const ll &v = 1, const ll &ep = 0) {
for (auto &u : g[v]) if (u.first != anc[v][0]) tala[v] += what_the_fuck(u.first, u.second);
if (ep && tala[v] >= k) A.push_back(ep);
return tala[v];
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>> n >> m >> k;
for (ll i = 1, v, u; i < n; i++) cin>> v >> u, g[v].push_back({u, i}), g[u].push_back({v, i});
DFS();
for (ll s; m--;) {
cin >> s;
A.resize(s);
for (auto &x : A) cin >> x;
add(s);
}
A.clear();
what_the_fuck();
sort(A.begin(), A.end());
cout<< A.size() << endl;
for (auto i : A) cout<< i << ' ';
return 0;
}
/*
_ _ _ _ _ _ _ _ _ _ _ _
/ / \ / / | / / |
/``````\ \ |`````| | |`````| |
/ \ \ | | | | | |
/ \ \ | | | | | |
/ /\ \ \ | | | | | |
/ / /\ \ \ | | | | | |
/ / / \ \ \ | | | | | |
/ / /_ _ \ \ \ | | | | | |
/ /_ _ _ _ \ \ \ | | | | | |
/ \ \ | | |_ _ _ _ | | |
/ _ _ _ _ _ _ _ \ \ | | / /| | | |
/ / / \ \ \ | |/_ _ _ _ / | | | |
/ / / \ \ / | | / | | /
/_ _ _/_/ \_ _ _\/ |_ _ _ _ _ _ _ _|/ |_ _ _|/
*/