Submission #1007978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007978		michified	Railway (BOI17_railway)	C++17	0 / 100	1065 ms	143760 KiB

railway

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

struct node_t {
	vector<int> anc, childs;
	vector<vector<int>> path;
	int depth;
};

vector<vector<pair<int, int>>> adj;
vector<node_t> tree;

void buildTree(int cur) {
	for (auto& p : adj[cur]) {
		if (not tree[cur].anc.empty() and tree[cur].anc[0] == p.first) continue;
		tree[p.first].anc.push_back(cur);
		tree[p.first].path.push_back({p.second});
		tree[cur].childs.push_back(p.first);
		tree[p.first].depth = tree[cur].depth + 1;
		buildTree(p.first);
	}
}

void buildAnc(int cur) {
	int id = tree[cur].anc[0], step = 0;
	while (tree[id].anc.size() >= step + 1) {
		tree[cur].path.push_back({});
		for (int road : tree[id].path[step]) tree[cur].path.back().push_back(road);
		id = tree[id].anc[step];
		tree[cur].anc.push_back(id);
		step++;
	}
	for (int child : tree[cur].childs) buildAnc(child);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m, k, i, j, tmp, tmp2;
	cin >> n >> m >> k;
	adj.resize(n + 1);
	for (i = 1; i <= n - 1; i++) {
		cin >> tmp >> tmp2;
		adj[tmp].push_back(make_pair(tmp2, i));
		adj[tmp2].push_back(make_pair(tmp, i));
	}
	vector<vector<int>> ms(m);
	for (i = 0; i < m; i++) {
		cin >> tmp;
		ms[i].resize(tmp);
		for (j = 0; j < tmp; j++) cin >> ms[i][j];
	}
	tree.resize(n + 1);
	buildTree(1);
	for (int child : tree[1].childs) buildAnc(child);
	vector<int> cnt(n + 1);
	for (auto& mi : ms) {
		// find LCA of all selected cities
		int LCA = mi[0], tu, tv, pos;
		for (int city : mi) {
			if (city == 1) {
				LCA = 1;
				break;
			}
			tu = LCA;
			tv = city;
			if (tree[tu].depth > tree[tv].depth) swap(tu, tv);
			pos = tree[tv].anc.size() - 1;
			while (tree[tv].depth > tree[tu].depth) {
				while (tree[tree[tv].anc[pos]].depth < tree[tu].depth) pos--;
				tv = tree[tv].anc[pos];
			}
			if (tv == tu) {
				LCA = tu;
				continue;
			}
			pos = tree[tv].anc.size() - 1;
			while (true) {
				while (pos >= 0 and tree[tv].anc[pos] == tree[tu].anc[pos]) pos--;
				if (pos < 0) break;
				tu = tree[tu].anc[pos];
				tv = tree[tv].anc[pos];
			}
			LCA = tree[tu].anc[0];
		}
		unordered_set<int> req;
		for (int city : mi) {
			pos = tree[city].anc.size() - 1;
			while (city != LCA) {
				while (pos >= 0 and (pos >= tree[city].anc.size() or tree[tree[city].anc[pos]].depth < tree[LCA].depth)) pos--;
				for (int i = 0; i <= pos; i++) {
					for (int road : tree[city].path[i]) req.insert(road);
				}
				city = tree[city].anc[pos];
			}
		}
		for (int elem : req) cnt[elem]++;
	}

	int ans = 0;
	for (i = 0; i <= n; i++) {
		if (cnt[i] >= k) ans++;
	}
	cout << ans << endl;
	for (i = 0; i <= n; i++) {
		if (cnt[i] >= k) cout << i << ' ';
	}
	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void buildAnc(int)':
railway.cpp:27:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |  while (tree[id].anc.size() >= step + 1) {
      |         ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:92:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     while (pos >= 0 and (pos >= tree[city].anc.size() or tree[tree[city].anc[pos]].depth < tree[LCA].depth)) pos--;
      |                          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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