Submission #1008020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008020		michified	Railway (BOI17_railway)	C++17	100 / 100	248 ms	43196 KiB

railway

#include <bits/stdc++.h>
#define ll long long
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;

struct node_t {
	vector<int> anc, childs;
	int depth, tin, tout, parrid;
};

vector<vector<pair<int, int>>> adj;
vector<node_t> tree;
vector<int> st;
int t = 0;

void buildTree(int cur) {
	tree[cur].tin = t;
	t++;
	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].parrid = p.second;
		tree[cur].childs.push_back(p.first);
		tree[p.first].depth = tree[cur].depth + 1;
		buildTree(p.first);
	}
	tree[cur].tout = t;
	t++;
}

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

int findLCA(int a, int b) {
	if (tree[a].depth > tree[b].depth) swap(a, b);
	if (a == 1) return 1;
	int pos = tree[b].anc.size() - 1;
	while (tree[b].depth > tree[a].depth) {
		while (pos >= tree[b].anc.size() or tree[tree[b].anc[pos]].depth < tree[a].depth) pos--;
		b = tree[b].anc[pos];
	}
	if (a == b) return a;
	pos = tree[a].anc.size() - 1;
	while (true) {
		while (pos >= 0 and (pos >= tree[a].anc.size() or tree[a].anc[pos] == tree[b].anc[pos])) pos--;
		if (pos < 0) break;
		a = tree[a].anc[pos];
		b = tree[b].anc[pos];
	}
	return tree[a].anc[0]; 
}

int que(int id, int l, int r, int ql, int qr) {
	if (l > qr or r < ql) return 0;
	if (ql <= l and r <= qr) return st[id];
	int mid = (l + r) / 2;
	return que(lid, l, mid, ql, qr) + que(rid, mid + 1, r, ql, qr); 
}

void upd(int id, int l, int r, int pos, int val) {
	if (l == r) {
		st[id] += val;
		return;
	}
	int mid = (l + r) / 2;
	if (pos <= mid) upd(lid, l, mid, pos, val);
	else upd(rid, mid + 1, r, pos, val);
	st[id] = st[lid] + st[rid];
}

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);
	st.resize(t * 4);
	for (auto& mi : ms) {
		sort(mi.begin(), mi.end(), [](const int a, const int b){return tree[a].tin < tree[b].tin;});
		mi.push_back(mi[0]);
		for (i = 0; i < mi.size() - 1; i++) {
			upd(0, 0, t - 1, tree[mi[i]].tin, 1);
			upd(0, 0, t - 1, tree[mi[i]].tout, 1);
			upd(0, 0, t - 1, tree[mi[i + 1]].tin, 1);
			upd(0, 0, t - 1, tree[mi[i + 1]].tout, 1);
			upd(0, 0, t - 1, tree[findLCA(mi[i], mi[i + 1])].tin, -2);
			upd(0, 0, t - 1, tree[findLCA(mi[i], mi[i + 1])].tout, -2);
		}
	}
	vector<int> ans;
	for (i = 2; i <= n; i++) {
		if (que(0, 0, t - 1, tree[i].tin, tree[i].tout) / 2 >= k * 2) ans.push_back(tree[i].parrid);
	}
	sort(ans.begin(), ans.end());
	cout << ans.size() << endl;
	for (int r : ans) cout << r << ' ';
	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void buildAnc(int)':
railway.cpp:34:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |  while (tree[id].anc.size() >= step + 1) {
      |         ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
railway.cpp: In function 'int findLCA(int, int)':
railway.cpp:47:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   while (pos >= tree[b].anc.size() or tree[tree[b].anc[pos]].depth < tree[a].depth) pos--;
      |          ~~~~^~~~~~~~~~~~~~~~~~~~~
railway.cpp:53:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   while (pos >= 0 and (pos >= tree[a].anc.size() or tree[a].anc[pos] == tree[b].anc[pos])) pos--;
      |                        ~~~~^~~~~~~~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:104:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for (i = 0; i < mi.size() - 1; 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