Submission #777655

#	Time	Username	Problem	Language	Result	Execution time	Memory
777655		NK_	Railway (BOI17_railway)	C++17	100 / 100	230 ms	47548 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

template<class T> struct BIT {
	vector<int> data; int N; 
	void init(int n) { N = n; data = vector<int>(N, 0); }
	void add(int p, int x) { for(++p;p<=N;p+=p&-p) data[p-1] += x; }
	int sum(int l, int r) { return sum(r+1) - sum(l); }
	int sum(int r) { int s = 0; for(;r;r-=r&-r) s += data[r-1]; return s; }
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	

	int N, M, K; cin >> N >> M >> K;

	vector<vector<int>> adj(N);

	map<pair<int, int>, int> idx;
	for(int i = 0; i < N-1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		idx[{u, v}] = idx[{v, u}] = i;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	const int LG = 20;

	vector<vector<int>> up(N, vector<int>(LG));
	vector<int> dep(N), st(N), en(N);

	int t = 0;
	function<void(int, int)> gen = [&](int u, int p) {
		up[u][0] = (p == -1 ? u : p);
		for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1];

		dep[u] = (p == -1 ? 0 : dep[p]+1);
		st[u] = t++;
		for(auto v : adj[u]) if (v != p) gen(v, u);
		en[u] = t-1;
	};

	gen(0, -1);

	auto jmp = [&](int u, int d) {
		for(int i = 0; i < LG; i++) if ((d >> i) & 1) u = up[u][i];
		return u;
	};

	auto lca = [&](int u, int v) {
		if (dep[u] < dep[v]) swap(u, v);
		u = jmp(u, dep[u] - dep[v]);

		if (u == v) return u;
		for(int i = LG - 1; i >= 0; i--) {
			int U = up[u][i], V = up[v][i];
			if (U != V) u = U, v = V;
		}

		return up[u][0];
	};

	vector<int> C(N);

	BIT<int> B; B.init(N);
	for(int q = 0; q < M; q++) {
		int k; cin >> k;
		vector<int> A(k); for(auto &x : A) { cin >> x; --x; }

		sort(begin(A), end(A), [&](int x, int y) {
			if (en[x] == en[y]) return dep[x] > dep[y];
			return en[x] < en[y];
		});

		int all = A[0];
		// cout << q << " - " << k << nl;
		for(auto x : A) {
			all = lca(all, x);
			B.add(st[x], 1);
			C[x]++;
			// cout << x << " ";
		}
		// cout << nl;

		vector<int> L = A;
		for(int i = 0; i < k-1; i++) {
			L.push_back(lca(A[i], A[i+1]));
		}

		sort(begin(L), end(L));
		L.erase(unique(begin(L), end(L)), end(L));

		sort(begin(L), end(L), [&](int x, int y) {
			if (en[x] == en[y]) return dep[x] > dep[y];
			return en[x] < en[y];
		});

		// cout << "NODES: " << nl;
		for(auto x : L) {
			int amt = B.sum(st[x], en[x]) - 1;
			// cout << x << " => " << amt << nl;
			B.add(st[x], -amt);
			C[x] -= amt;
		}
		// cout << nl;

		C[all]--;
		// cout << "LCA: " << all << nl;

		for(auto x : L) B.add(st[x], -B.sum(st[x], st[x]));
	}

	vector<int> ans;
	function<void(int, int)> dfs = [&](int u, int p) {
		for(auto v : adj[u]) if (v != p) {
			dfs(v, u);
			C[u] += C[v];
		}
		// cout << u << " -> " << C[u] << nl;

		if (p != -1 && C[u] >= K) ans.push_back(idx[{u, p}]);
	};

	dfs(0, -1);

	sort(begin(ans), end(ans));

	cout << size(ans) << nl;
	for(auto x : ans) cout << x+1 << " ";
	cout << nl;



		

    return 0;
}

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