Submission #931101

#	Time	Username	Problem	Language	Result	Execution time	Memory
931101		yellowtoad	Railway (BOI17_railway)	C++17	100 / 100	145 ms	24592 KiB

railway

#include <iostream>
#include <vector>
#include <algorithm>
#define f first
#define s second
using namespace std;

int n, m, test, k, pre[100010], d[100010], p[100010][20], lst[100010], cnt, diff[100010];
vector<pair<int,int>> edge[100010], node;
vector<int> stk, ans;

void dfs(int u, int v, int depth, int previd) {
	pre[u] = ++cnt;
	d[u] = depth;
	lst[u] = previd;
	p[u][0] = v;
	for (int i = 1; i < 20; i++) p[u][i] = p[p[u][i-1]][i-1];
	for (int i = 0; i < edge[u].size(); i++) if (edge[u][i].f != v) dfs(edge[u][i].f,u,depth+1,edge[u][i].s);
}

int lca(int u, int v) {
	if (d[u] < d[v]) swap(u,v);
	int i = 19;
	while (i >= 0) {
		if (d[p[u][i]] >= d[v]) u = p[u][i];
		i--;
	}
	if (u == v) return u;
	i = 19;
	while (i >= 0) {
		if (p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
		i--;
	}
	return p[u][0];
}

void dfs1(int u, int v) {
	for (int i = 0; i < edge[u].size(); i++) {
		if (edge[u][i].f != v) {
			dfs1(edge[u][i].f,u);
			diff[lst[u]] += diff[lst[edge[u][i].f]];
		}
	}
}

int main() {
	cin >> n >> test >> k;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		edge[u].push_back({v,i});
		edge[v].push_back({u,i});
	}
	dfs(1,0,1,0);
	//for (int i = 1; i <= n; i++) cout << pre[i] << endl;
	for (int i = 1; i <= test; i++) {
		cin >> m;
		node.clear(); stk.clear();
		for (int j = 1; j <= m; j++) {
			int x;
			cin >> x;
			node.push_back({pre[x],x});
		}
		sort(node.begin(),node.end());
		stk.push_back(node[0].s);
		for (int j = 1; j < m; j++) {
			int lcaa = lca(stk.back(),node[j].s);
			//cout << lcaa << " " << stk.back() << " " << node[j].s << endl;
			while ((stk.size()) && (d[stk.back()] > d[lcaa])) {
				//cout << stk.back() << endl;
				diff[lst[stk.back()]]++;
				stk.pop_back();
				if ((stk.size()) && (d[stk.back()] > d[lcaa])) diff[lst[stk.back()]]--;
				else diff[lst[lcaa]]--;
			}
			if (!((stk.size()) && (stk.back() == lcaa))) stk.push_back(lcaa);
			if (lcaa != node[j].s) stk.push_back(node[j].s);
		}
		while (stk.size() > 1) {
			diff[lst[stk.back()]]++;
			stk.pop_back();
			diff[lst[stk.back()]]--;
		}
		//cout << endl;
	}
	//for (int i = 1; i < n; i++) cout << diff[i] << endl;
	dfs1(1,0);
	for (int i = 1; i < n; i++) if (diff[i] >= k) ans.push_back(i);
	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); i++) {
		if (i) cout << " ";
		cout << ans[i];
	}
	if (ans.size()) cout << endl;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int, int, int)':
railway.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i = 0; i < edge[u].size(); i++) if (edge[u][i].f != v) dfs(edge[u][i].f,u,depth+1,edge[u][i].s);
      |                  ~~^~~~~~~~~~~~~~~~
railway.cpp: In function 'void dfs1(int, int)':
railway.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i = 0; i < edge[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for (int i = 0; i < ans.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