Submission #697421

#	Time	Username	Problem	Language	Result	Execution time	Memory
697421		d4xn	Railway (BOI17_railway)	C++17	7 / 100	119 ms	37684 KiB

railway

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

#define int long long


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

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

void dfs(int u, int par, int id, int d) {
	dep[u] = d;
	pre[u] = tim++;
	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;
		set<int> tims;
		vector<pair<int, int>> ordP(x), ordD(x);
		for (int i = 0; i < x; i++) {
			int y;
			cin >> y;
			y--;
			tims.insert(pre[y]);
			ordP[i] = make_pair(pre[y], y);
			ordD[i] = make_pair(dep[y], y);
		}
		//sort(tims.begin(), tims.end());
		sort(ordP.begin(), ordP.end());
		sort(ordD.rbegin(), ordD.rend());

		for (int i = 0; i < x; i++) {
			int y = ordD[i].second;
			f[y]++;
			auto l = tims.upper_bound(pre[y]);
			//int r = lower_bound(tims.begin(), tims.end(), pre[y]+sz[y]);
			
			vector<int> to_erase;
			for (; l != tims.end(); l++) {
				if (*l >= pre[y]+sz[y]) break;
				f[y]--;
				to_erase.push_back(*l);
			}
			for (int& j : to_erase) tims.erase(j);
		}

		int l = ordP[0].second;
		int r = ordP.back().second;
		f[lca(l, r)]--;
	}

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

  vector<int> ans;
  for (int i = 0; i < n; i++) {
    int x = ordD[i].second;
    if (f[x] >= k) ans.push_back(upId[x]);
    f[up[0][x]] += f[x];
  }
  sort(ans.begin(), ans.end());

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

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