Submission #714680

#	Time	Username	Problem	Language	Result	Execution time	Memory
714680		Melika0gh	Railway (BOI17_railway)	C++17	100 / 100	144 ms	27964 KiB

railway

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define sync        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pb          push_back
#define mp          make_pair
#define fi          first
#define se          second

const int maxn = 2e5 + 10, mood = 1e9 + 7, maxsq = 400, maxlg = 21;
//const int mood2 = 97277821, mood3 = 34098487, base = 31;
vector<int> adj[maxn];
vector<pair<int, int> > edge;
int anc[maxn][maxlg];
int st[maxn], ft[maxn], cnt[maxn], h[maxn];
int n, m, k, t;

void Dfs(int v = 1, int par = -1)
{
	st[v] = ++t;
	for(int i = 1; i < maxlg; i++)
	{
		anc[v][i] = anc[anc[v][i-1]][i-1];
	}
	for(auto u : adj[v]) if(u != par)
	{
		h[u] = h[v] + 1;
		anc[u][0] = v;
		Dfs(u, v);
	}
	ft[v] = t;
}

void Dfs2(int v = 1, int par = -1)
{
	for(auto u : adj[v]) if(u != par)
	{
		Dfs2(u, v);
		cnt[v] += cnt[u];
	}
	return;
}

int Up(int u, int d)
{
	for(int i = 0; i < maxlg; i++)
	{
		if((d >> i) & 1)
			u = anc[u][i];
	}
	return u;
}

int  Lca(int u, int v)
{
	if(h[u] < h[v])
		swap(u, v);
	
	u = Up(u, h[u] - h[v]);
	
	for(int i = maxlg - 1; i >= 0; i--)
	{
		if(anc[u][i] != anc[v][i])
		{
			u = anc[u][i];
			v = anc[v][i];
		}
	}
	
	if(v == u)
		return v;
	return anc[v][0];
}

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

int main()
{
	sync;
	cin >> n >> m >> k;
	for(int i = 0; i < n-1; i++)
	{
		int u, v;
		cin >> u >> v;
		edge.pb(mp(u, v));
		adj[u].pb(v);
		adj[v].pb(u);
	}
	Dfs();
	for(int i = 0; i < m; i++)
	{
		vector<int> vec;
		int s;
		cin >> s;
		for(int j = 0; j < s; j++)
		{
			int x;
			cin >> x;
			vec.pb(x);
		}
		sort(vec.begin(), vec.end(), cmp);
		
		for(int j = 0; j < (int)vec.size(); j++)
		{
			int v = vec[j], u = vec[(j+1) % s];
			cnt[v]++;
			int lca = Lca(v, u);
			cnt[lca]--;
		}
	}
	Dfs2();
	vector<int> ans;
	for(int i = 0; i < n-1; i++)
	{
		int u = edge[i].fi, v = edge[i].se;
		if(h[u] < h[v])
			swap(u, v);
			
		if(cnt[u] >= k)
		{
			ans.pb(i+1);
		}
	}
	
	cout << (int)ans.size() << '\n';
	for(int x : ans)
		cout << x << ' ';
	
	cout << '\n';
	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