Submission #439668

#	Time	Username	Problem	Language	Result	Execution time	Memory
439668		Ya_Ali	Railway (BOI17_railway)	C++17	100 / 100	165 ms	34208 KiB

railway

/* ** *** 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;
}
/*
		  _ _ _ _                  _ _ _ _                _ _ _ _
		/      / \                /     / |              /     / |
	       /``````\   \              |`````|  |             |`````|  |
	      /        \   \             |     |  |             |     |  |
	     /          \   \            |     |  |             |     |  |
	    /     /\     \   \           |     |  |             |     |  |
	   /     / /\     \   \          |     |  |             |     |  |
	  /     / /  \     \   \         |     |  |             |     |  |
	 /     / /_ _ \     \   \        |     |  |             |     |  |
	/     /_ _ _ _ \     \   \       |     |  |             |     |  |
       /                      \   \      |     |  |_ _ _ _      |     |  |
      /      _ _ _ _ _ _ _     \   \     |     | /        /|    |     |  |
     /     / /            \     \   \    |     |/_ _ _ _ / |    |     |  |
    /     / /              \     \  /    |               | /    |     | /
   /_ _ _/_/                \_ _ _\/     |_ _ _ _ _ _ _ _|/     |_ _ _|/
*/

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25