Submission #1039139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039139		___	Railway (BOI17_railway)	C++17	100 / 100	115 ms	39096 KiB

railway

#include <bits/stdc++.h>
#define int long long int
#define ff first
#define ss second
#define FT ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int maxn = 1e5 + 10;
const int mxlg = 25;
vector <int> adj[maxn];
int st[maxn] , cnt , f[maxn] , p[maxn][mxlg] , h[maxn];
pair <int , int> edge[maxn];
vector <int> ans;
///////////////////////////////////////////////////////
void dfs (int v , int g)
{
	st[v] = ++cnt;
	p[v][0] = g;
	h[v] = h[g] + 1;
	for (int i = 1 ; i < mxlg ; i++)
	{
		int x = p[v][i - 1];
		p[v][i] = p[x][i - 1];
	}
	for (auto u : adj[v])
	{
		if (u != g)
		{
			dfs(u , v);
			f[v] += f[u];
		}
	}
}
//////////////////////////////////////////////////////////
int lca (int a , int b)
{
	if (h[b] > h[a])
	{
		swap (a , b);
	}
	for (int i = mxlg - 1 ; i >= 0 ; i--)
	{
		if (h[p[a][i]] >= h[b])
		{
			a = p[a][i];
		}
	}
	if (a == b)
	{
		return a;
	}
	for (int i = mxlg - 1 ; i >= 0 ; i--)
	{
		if (p[a][i] != p[b][i])
		{
			a = p[a][i];
			b = p[b][i];
		}
	}
	return p[a][0];
}
//////////////////////////////////////////////////////////////
signed main() {
	FT;
	int n , m , k;
	cin >> n >> m >> k;
	for (int i = 1 ; i < n ; i++)
	{
		int a , b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
		edge[i] = {a , b};
	}
	dfs (1 , 0);
	for (int i = 1 ; i <= m ; i++)
	{
		vector <pair <int , int>> S;
		int sz;
		cin >> sz;
		for (int j = 1 ; j <= sz ; j++)
		{
			int x;
			cin >> x;
			S.push_back({st[x] , x});
		}
		sort (S.begin() , S.end());
		for (int j = 0 ; j < sz - 1 ; j++)
		{
			f[S[j].ss]++;
			f[S[j + 1].ss]++;
			f[lca (S[j].ss , S[j + 1].ss)] -= 2;
		}
		f[S[0].ss]++;
		f[S[sz - 1].ss]++;
		f[lca (S[0].ss , S[sz - 1].ss)] -= 2;
	}
	dfs (1 , 0);
	for (int i = 1 ; i < n ; i++)
	{
		int u = edge[i].ff , v = edge[i].ss;
		if (h[v] < h[u])
		{
			swap (u , v);
		}
		if (f[v] >= 2 * k)
		{
			ans.push_back(i);
		}
	}
	cout << ans.size() << endl;
	for (auto i : ans)
	{
		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