Submission #378259

#	Time	Username	Problem	Language	Result	Execution time	Memory
378259		Nima_Naderi	Railway (BOI17_railway)	C++14	100 / 100	262 ms	33756 KiB

railway

///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 1e5 + 10;
const ll LOG = 17;
ll n, q, m, k, timer;
ll Stm[MXN], val[MXN];
ll Jad[LOG][MXN], dis[MXN];
vector<pair<ll, ll>> Edge;
vector<ll> adj[MXN], S, ANS;
void prep(ll u, ll par){
	Jad[0][u] = par, Stm[u] = ++ timer;
	for(int i = 1; i < LOG; i ++) Jad[i][u] = Jad[i - 1][Jad[i - 1][u]];
	for(auto v : adj[u]){
		if(v != par) dis[v] = dis[u] + 1, prep(v, u);
	}
}
ll K_Jad(ll u, ll k){
	for(int i = 0; i < LOG; i ++){
		if((k >> i) & 1LL) u = Jad[i][u];
	}
	return u;
}
ll LCA(ll u, ll v){
	if(dis[u] > dis[v]) swap(u, v);
	v = K_Jad(v, dis[v] - dis[u]);
	if(u == v) return u;
	for(int i = LOG - 1; ~i; i --){
		if(Jad[i][u] != Jad[i][v]){
			u = Jad[i][u], v = Jad[i][v];
		}
	}
	return Jad[0][u];
}
void Add(ll u, ll v){
	ll lca = LCA(u, v);
	val[u] ++, val[v] ++, val[lca] -= 2;
	//cout << "Q : " << u << ' ' << v << " -> " << lca << '\n';
}
void Arch(){
	sort(S.begin(), S.end(), [&](const int &u, const int &v){
		return Stm[u] < Stm[v];
	});
	for(int i = 0; i < m - 1; i ++) Add(S[i], S[i + 1]);
	Add(S[0], S[m - 1]);
}
void flood(ll u, ll par){
	for(auto v : adj[u]){
		if(v != par){
			flood(v, u);
			val[u] += val[v];
		}
	}
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> q >> k; k *= 2;
	for(int i = 1; i < n; i ++){
		ll u, v; cin >> u >> v;
		adj[u].push_back(v), adj[v].push_back(u);
		Edge.push_back({u, v});
	}
	prep(1, 0);
	//for(int i = 1; i <= n; i ++) cout << Stm[i] << ' '; cout << '\n';
	for(int i = 1; i <= q; i ++){
		S.clear(); cin >> m;
		for(int j = 0; j < m; j ++){
			ll u; cin >> u;
			S.push_back(u);
		}
		Arch();
	}
	flood(1, 0);
	int id = 0;
	for(auto e : Edge){
		ll u, v; tie(u, v) = e; id ++;
		if(dis[u] > dis[v]) swap(u, v);
		if(val[v] >= k) ANS.push_back(id);
	}
	cout << ANS.size() << '\n';
	for(auto X : ANS) cout << X << ' ';
	cout << '\n';
	return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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