Submission #714621

#	Time	Username	Problem	Language	Result	Execution time	Memory
714621		parsadox2	Railway (BOI17_railway)	C++14	100 / 100	219 ms	22476 KiB

railway

#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define wall 		cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 10 , maxl = 18;
int n , m , k , par[maxl][maxn] , h[maxn] , st[maxn] , tim , val[maxn];
vector <int> adj[maxn];
vector <pair<int , int>> edges;

void dfs(int v)
{
	st[v] = tim++;
	for(auto u : adj[v])  if(u != par[0][v])
	{
		par[0][u] = v;
		h[u] = h[v] + 1;
		dfs(u);
	}
}

bool cmp(int a , int b)
{
	return st[a] < st[b];
}

int lca(int v , int u)
{
	if(h[v] < h[u])  swap(v , u);
	for(int i = 0 ; i < maxl ; i++)  if(((h[v] - h[u]) >> i) & 1)
		v = par[i][v];
	if(v == u)  return v;
	for(int i = maxl - 1 ; i > -1 ; i--)  if(par[i][v] != par[i][u])
	{
		v = par[i][v];
		u = par[i][u];
	}
	return par[0][v];
}

void update(int v)
{
	for(auto u : adj[v])  if(u != par[0][v])
	{
		update(u);
		val[v] += val[u];
	}
}

int32_t main()
{
	fast;
	cin >> n >> m >> k;
	for(int i = 0 ; i < n - 1 ; i++)
	{
		int v , u;  cin >> v >> u;
		adj[v].pb(u);  adj[u].pb(v);
		edges.pb({u , v});
	}
	dfs(1);
	for(int i = 1 ; i < maxl ; i++)
		for(int j = 1 ; j <= n ; j++)
			par[i][j] = par[i - 1][par[i - 1][j]];
	while(m--)
	{
		vector <int> vec;
		int s;  cin >> s;
		while(s--)
		{
			int x;  cin >> x; vec.pb(x);
			val[x]++;
		}
		sort(vec.begin() , vec.end() , cmp);
		for(int i = 0 ; i < SZ(vec) ; i++)
		{
			int a = vec[i] , b = vec[(i + 1) % SZ(vec)];
			int l = lca(a , b);
			val[l]--;
		}
	}
	update(1);
	vector <int> ans;
	for(int i = 0 ; i < n - 1 ; i++)
	{
		auto u = edges[i];
		int a = u.F , b = u.S;
		if(h[a] < h[b])  swap(a , b);
		if(val[a] >= k)  ans.pb(i + 1);
	}
	cout << SZ(ans) << endl;
	for(auto u : ans)  cout << u << " ";
	cout << endl;
	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