제출 #1316380

#제출 시각아이디문제언어결과실행 시간메모리
1316380blackscreen1Railway (BOI17_railway)C++20
100 / 100
80 ms36272 KiB
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, m, t, g;
vector<ll> adj[100005];
ll pre[100005], unpre[100005], cnt = 0;
ll ccnt[100005], ced[100005];
ll twok[100005][20], dpt[100005];
pll a[100005];
void dfs1(ll nd, ll pr, ll dp) {
	dpt[nd] = dp;
	twok[nd][0] = pr;
	iloop(1, 20) {
		if (twok[nd][i-1] == -1) break;
		twok[nd][i] = twok[twok[nd][i-1]][i-1];
	}
	unpre[cnt] = nd;
	pre[nd] = cnt++;
	for (auto it : adj[nd]) if (it != pr) dfs1(it, nd, dp+1);
}
ll lca(ll x, ll y) {
	if (dpt[x] < dpt[y]) swap(x, y);
	iloop(19, -1) if ((dpt[x] - dpt[y])&(1<<i)) {
		x = twok[x][i];
	}
	if (x == y) return x;
	iloop(19, -1) if (twok[x][i] != twok[y][i]) {
		x = twok[x][i];
		y = twok[y][i];
	}
	return twok[x][0];
}
vector<ll> ans;
ll dfs2(ll nd, ll pr) {
	ll cv = ccnt[nd];
	for (auto it : adj[nd]) if (it != pr) cv += dfs2(it, nd);
	if (cv >= t) ans.push_back(ced[nd]);
	return cv;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	memset(twok, -1, sizeof(twok));
	cin >> n >> m >> t;
	ll t1, t2;
	iloop(1, n) {
		cin >> t1 >> t2;
		t1--, t2--;
		a[i] = {t1, t2};
		adj[t1].push_back(t2);
		adj[t2].push_back(t1);
	}
	dfs1(0, -1, 0);
	iloop(1, n) {
		if (dpt[a[i].first] < dpt[a[i].second]) swap(a[i].first, a[i].second);
		ced[a[i].first] = i;
	}
	iloop(0, m) {
		cin >> g;
		vector<ll> v;
		jloop(0, g) {
			cin >> t1;
			t1--;
			ccnt[t1]++;
			v.push_back(pre[t1]);
		}
		sort(v.begin(), v.end());
		jloop(0, g) ccnt[lca(unpre[v[j]], unpre[v[(j+1)%g]])]--;	
	}
	dfs2(0, -1);
	if (ans.size()) sort(ans.begin(), ans.end());
	cout << ans.size() << "\n";
	for (auto it : ans) cout << it << " ";
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...