Submission #697545

#	Time	Username	Problem	Language	Result	Execution time	Memory
697545		d4xn	Railway (BOI17_railway)	C++17	100 / 100	232 ms	41312 KiB

railway

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5, L = 20;

int n, m, k, tim, dep[N], sz[N], pre[N], pos[N], upId[N], up[L][N];
vector<pair<int, int>> adj[N];
vector<int> End[N];
set<int> st[N];

void dfs(int u, int par, int id, int d) {
	pre[u] = tim;
  pos[tim] = u;
  tim++;
  
  dep[u] = d;
	sz[u] = 1;
	upId[u] = id;
	up[0][u] = par;
	for (auto& [v, idx] : adj[u]) {
		if (v == par) continue;
		dfs(v, u, idx, d + 1);
		sz[u] += sz[v];
	}
}

int lca(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	int dif = dep[x] - dep[y];
	for (int b = 0; b < L; b++) {
		if (dif & (1 << b))
			x = up[b][x];
	}
	if (x == y) return x;

	for (int b = L - 1; b >= 0; b--) {
		if (up[b][x] == up[b][y]) continue;
		x = up[b][x];
		y = up[b][y];
	}
	return up[0][x];
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m >> k;
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		adj[x].push_back(make_pair(y, i));
		adj[y].push_back(make_pair(x, i));
	}
	tim = 0;
	dfs(0, 0, -1, 0);

	for (int j = 1; j < L; j++) {
		for (int i = 0; i < n; i++) {
			up[j][i] = up[j - 1][up[j - 1][i]];
		}
	}

	while (m--) {
		int x;
		cin >> x;

		vector<int> v(x), ord(x);
		for (int i = 0; i < x; i++) {
			cin >> v[i];
			v[i]--;
			ord[i] = pre[v[i]];
		}
		sort(ord.begin(), ord.end());

		for (int i = 0; i < x; i++) {
			int y = v[i];
      /*
			auto l = upper_bound(ord.begin(), ord.end(), pre[y]);
			if (l != ord.end() && *l < pre[y] + sz[y]) continue;
      */
			st[y].insert(m);
		}

    int l = pos[ord[0]];
    int r = pos[ord.back()];
    End[lca(l, r)].push_back(m);
    //cerr << lca(l, r)+1 << endl;
	}

	vector<pair<int, int>> ord(n);
	for (int i = 0; i < n; i++) {
		ord[i] = make_pair(dep[i], i);
	}
	sort(ord.rbegin(), ord.rend());

	vector<int> ans;
	for (int i = 0; i < n-1; i++) {
		int x = ord[i].second;
    //cerr << x+1 << " " << st[x].size() << endl;
    for (int& y : End[x]) st[x].erase(y);
    //cerr << x+1 << " " << st[x].size() << endl;

		if (st[x].size() >= k) ans.push_back(upId[x]);

		int p = up[0][x];
		if (st[x].size() > st[p].size()) swap(st[x], st[p]);
		for (int y : st[x]) st[p].insert(y);
		st[x].clear();
	}
	sort(ans.begin(), ans.end());

	cout << ans.size() << "\n";
	for (int &i : ans) {
		cout << i+1 << " ";
	}
	cout << "\n";
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:107:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |   if (st[x].size() >= k) ans.push_back(upId[x]);
      |       ~~~~~~~~~~~~~^~~~

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