Submission #866427

#	Time	Username	Problem	Language	Result	Execution time	Memory
866427		serifefedartar	Railway (BOI17_railway)	C++17	100 / 100	81 ms	26064 KiB

railway

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20; 
const ll MAXN = 1e5 + 5;

vector<vector<pair<int,int>>> graph;
vector<int> ans;
int tin[MAXN], tout[MAXN], depth[MAXN], up[LOGN][MAXN];
int T = 0, val[MAXN], k;
void dfs(int node, int parent) {
	tin[node] = ++T;
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		depth[u.f] = depth[node] + 1;
		up[0][u.f] = node;
		for (int i = 1; i < LOGN; i++)
			up[i][u.f] = up[i-1][up[i-1][u.f]];
		dfs(u.f, node);
	}
	tout[node] = T;
}

int find(int node, int k) {
	for (int i = 0; i < LOGN; i++) {
		if ((1<<i) & k)
			node = up[i][node];
	}
	return node;
}

int lca(int a, int b) {
	if (depth[b] > depth[a])
		swap(a, b);
	a = find(a, depth[a] - depth[b]);
	if (a == b)
		return a;

	for (int i = LOGN - 1; i >= 0; i--) {
		if (up[i][a] != up[i][b]) {
			a = up[i][a];
			b = up[i][b];
		}
	}
	return up[0][a];
}

int dfs2(int node, int parent_edge) {
	for (auto u : graph[node]) {
		if (u.s != parent_edge)
			val[node] += dfs2(u.f, u.s);
	}

	if (val[node] >= 2 * k && node != 1)
		ans.push_back(parent_edge);
	return val[node];
}

int main() {
	fast
	int n, m, a, b;
	cin >> n >> m >> k;

	graph = vector<vector<pair<int,int>>>(n+1, vector<pair<int,int>>());
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		graph[a].push_back({b, i});
		graph[b].push_back({a, i});
	}
	for (int i = 0; i < LOGN; i++)
		up[i][1] = 1;
	dfs(1, 1);

	int q, p;
	for (int i = 0; i < m; i++) {
		cin >> q;
		vector<int> all;
		for (int j = 0; j < q; j++) {
			cin >> p;
			all.push_back(p);
		}
		sort(all.begin(), all.end(), [&](int a, int b) {
			return tin[a] < tin[b];
		});
		all.push_back(all[0]); 

		for (int i = 1; i < all.size(); i++) {
			int lowest = lca(all[i-1], all[i]);
			val[lowest] -= 2;
			val[all[i-1]]++;
			val[all[i]]++;
		}
	}
	dfs2(1, -1);

	sort(ans.begin(), ans.end());
	cout << ans.size() << "\n";
	for (auto u : ans)
		cout << u << " ";
	cout << "\n";
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for (int i = 1; i < all.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