Submission #666718

#	Time	Username	Problem	Language	Result	Execution time	Memory
666718		Eae02	Railway (BOI17_railway)	C++17	100 / 100	237 ms	22644 KiB

railway

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
using namespace std;
using ll = long long;

struct HLD {
	vector<ll> depth, parent, arridx, hpLeaf, hpRoot, hchild;
	HLD(const vector<vector<ll>>& t) { // t is an adjacency list, or a child list for a tree rooted in node 0
		parent = hchild = vector<ll>(t.size(), -1);
		depth = arridx = hpLeaf = hpRoot = vector<ll>(t.size());
		vector<ll> sts(t.size(), 1), ci(t.size()), st{0}, trav{0};
		while (!st.empty()) {
			ll cur = st.back(), nx;
			if (ci[cur] == (ll)t[cur].size()) {
				st.pop_back();
				if (st.empty()) continue;
				sts[st.back()] += sts[cur];
				if (hchild[st.back()] == -1 || sts[cur] > sts[hchild[st.back()]])
					hchild[st.back()] = cur;
			} else if ((nx = t[cur][ci[cur]++]) != parent[cur]) {
				depth[nx] = depth[cur] + 1;
				parent[nx] = cur;
				st.push_back(nx);
				trav.push_back(nx);
			}
		}
		iota(all(hpRoot), 0);
		iota(all(hpLeaf), 0);
		ll nai = 0;
		for (ll cur : trav) {
			if (hchild[cur] == -1) {
				arridx[cur] = nai;
				nai += depth[cur] - depth[hpRoot[cur]] + 1;
			}
			else
				hpRoot[hchild[cur]] = hpRoot[cur];
		}
		for (ll i = trav.size() - 1; i >= 0; i--) {
			if (hchild[trav[i]] == -1) continue;
			arridx[trav[i]] = arridx[hchild[trav[i]]] + 1;
			hpLeaf[trav[i]] = hpLeaf[hchild[trav[i]]];
		}
	}
	ll lca(ll a, ll b, vector<pair<ll, ll>>* llv = nullptr, bool llvIncludeLCA = true) {
		auto sdepth = [&] (ll i) { return i == -1 ? -1 : depth[i]; };
		auto addi = [&] (ll lo, ll hi) { if (llv && lo != hi) llv->emplace_back(lo, hi); };
		while (hpRoot[a] != hpRoot[b]) {
			ll nxa = parent[hpRoot[a]];
			ll nxb = parent[hpRoot[b]];
			if (sdepth(nxa) > sdepth(nxb)) {
				addi(arridx[a], arridx[hpRoot[a]] + 1);
				a = nxa;
			} else {
				addi(arridx[b], arridx[hpRoot[b]] + 1);
				b = nxb;
			}
		}
		if (depth[a] > depth[b])
			swap(a, b);
		addi(arridx[b], arridx[a] + llvIncludeLCA);
		return a;
	}
};

int main() {
	ll numNodes, numMinist, reqMinist;
	cin >> numNodes >> numMinist >> reqMinist;
	
	vector<vector<ll>> adj(numNodes);
	adj.resize(numNodes);
	
	map<pair<ll, ll>, ll> trackIds;
	
	for (ll i = 0; i < numNodes - 1; i++) {
		ll a, b;
		cin >> a >> b;
		a--;
		b--;
		trackIds.emplace(make_pair(min(a, b), max(a, b)), i+1);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	HLD hld(adj);
	
	vector<ll> v(numNodes + 1);
	
	for (ll i = 0; i < numMinist; i++) {
		ll s, sel0;
		cin >> s >> sel0;
		
		if (s == 2) {
			ll sel1;
			cin >> sel1;
			vector<pair<ll, ll>> intv;
			hld.lca(sel0-1, sel1-1, &intv, false);
			for (auto [lo, hi] : intv) {
				v[lo]++;
				v[hi]--;
			}
		} else {
			vector<pair<ll, ll>> pts;
			for (ll j = 1; j < s; j++) {
				ll node;
				cin >> node;
				vector<pair<ll, ll>> intv;
				hld.lca(sel0-1, node-1, &intv, false);
				for (auto [lo, hi] : intv) {
					pts.emplace_back(lo, 1);
					pts.emplace_back(hi, -1);
				}
			}
			sort(all(pts));
			
			ll depth = 0;
			for (auto [x, d] : pts) {
				if (depth == 0) v[x]++;
				depth += d;
				if (depth == 0) v[x]--;
			}
		}
	}
	
	vector<ll> vps(numNodes + 1);
	for (ll i = 0; i < numNodes; i++)
		vps[i+1] = vps[i] + v[i];
	
	vector<ll> reqTracks;
	for (ll i = 1; i < numNodes; i++) {
		if (vps[hld.arridx[i]+1] >= reqMinist) {
			ll p = hld.parent[i];
			reqTracks.push_back(trackIds[{min(i, p), max(i, p)}]);
		}
	}
	
	sort(reqTracks.begin(), reqTracks.end());
	
	cout << reqTracks.size() << "\n";
	for (ll t : reqTracks) {
		cout << t << " ";
	}
	cout << "\n";
}

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