Submission #1027111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027111		aykhn	Railway (BOI17_railway)	C++17	100 / 100	56 ms	33476 KiB

railway

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

#define inf 0x3F3F3F3F3F3F3F3F
#define int long long

const int MXN = 1e5 + 5;
const int LOG = 18;

int n, m, k;
vector<array<int, 2>> adj[MXN];
int p[LOG][MXN];
int in[MXN], out[MXN], tim;
int rev[MXN], sum[MXN];
int ans[MXN];

void _init(int a)
{
	in[a] = ++tim;
	for (array<int, 2> &v : adj[a])
	{
		if (v[0] == p[0][a]) continue;
		p[0][v[0]] = a;
		_init(v[0]);
		rev[v[0]] = v[1];
	}
	out[a] = tim;
}
int anc(int u, int v)
{
	return in[u] <= in[v] && out[v] <= out[u];
}
int LCA(int u, int v)
{
	if (anc(u, v)) return u;
	if (anc(v, u)) return v;
	for (int i = LOG - 1; i >= 0; i--)
	{
		if (anc(p[i][u], v)) continue;
		u = p[i][u];
	}
	return p[0][u];
}

void dfs(int a)
{
	for (array<int, 2> &v : adj[a])
	{
		if (v[0] == p[0][a]) continue;
		dfs(v[0]);
		sum[a] += sum[v[0]];
	}
	ans[rev[a]] = sum[a];
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
	}
	_init(1);
	p[0][1] = 1;
	for (int i = 1; i < LOG; i++) for (int j = 1; j <= n; j++) p[i][j] = p[i - 1][p[i - 1][j]];
	while (m--)
	{
		int s;
		cin >> s;
		vector<int> v(s);
		for (int &i : v) cin >> i;
		sort(v.begin(), v.end(), [&](const int &a, const int &b)
		{
			return in[a] < in[b];
		});
		sum[LCA(v[0], v.back())]--, sum[v[0]]++;
		for (int i = 1; i < v.size(); i++)
		{
			int lca = LCA(v[i - 1], v[i]);
			sum[lca]--, sum[v[i]]++;
		}
	}
	dfs(1);
	vector<int> x;
	for (int i = 1; i < n; i++) if (ans[i] >= k) x.push_back(i);
	cout << x.size() << '\n';
	for (int &i : x) cout << i << ' ';
	cout << '\n';
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:83:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for (int i = 1; i < v.size(); i++)
      |                   ~~^~~~~~~~~~

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