Submission #304847

#	Time	Username	Problem	Language	Result	Execution time	Memory
304847		penguinhacker	Railway (BOI17_railway)	C++17	100 / 100	140 ms	22384 KiB

railway

//source: https://oj.uz/problem/view/BOI17_railway
#include <bits/stdc++.h>
using namespace std;

const int mxN = 100000, K = 17;
int n, m, k, id[mxN];
int tin[mxN], tout[mxN], timer = 0;
int anc[mxN][K];
vector<pair<int, int>> adj[mxN];

void dfs(int u = 0, int p = -1) {
	tin[u] = timer++;
	anc[u][0] = p;
	for (int i = 1; i < K; ++i) {
		anc[u][i] = anc[u][i - 1] == -1 ? -1 : anc[anc[u][i - 1]][i - 1];
	}
	for (pair<int, int> v : adj[u]) {
		if (v.first != p) {
			id[v.first] = v.second;
			dfs(v.first, u);
		}
	}
	tout[u] = timer++;
}

bool is_anc(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
	//assert(tin[a] <= tin[b]);
	if (is_anc(a, b)) {
		return a;
	}
	//cout << a << " " << b << " ";
	for (int i = K - 1; ~i; --i) {
		if (anc[a][i] != -1 && !is_anc(anc[a][i], b)) {
			a = anc[a][i];
		}
	}
	//cout << a << " " << anc[a][0] << "\n";
	return anc[a][0];
}

/*int bit[2 * mxN + 1];
void upd(int i, int val) {
	for (++i; i <= 2 * n; i += i & -i) {
		bit[i] += val;
	}
}

int qry(int a, int b) {
	int res = 0;
	for (++a; a > 0; a -= a & -a) {
		res += bit[a];
	}
	for (++b; b > 0; b -= b & -b) {
		res -= bit[b];
	}
	return res;
}*/
int cnt[2 * mxN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i < n; ++i) {
		int a, b;
		cin >> a >> b, --a, --b;
		adj[a].emplace_back(b, i);
		adj[b].emplace_back(a, i);
	}
	dfs();
	/*for (int i = 0; i < n; ++i) {
		cout << tin[i] << " " << tout[i] << "\n";
	}*/
	for (int i = 0; i < m; ++i) {
		int num;
		cin >> num;
		vector<int> pos(num);
		for (int& i : pos) {
			cin >> i, --i;
		}
		sort(pos.begin(), pos.end(), [](int a, int b) {return tin[a] < tin[b];});
		pos.push_back(pos[0]);
		//cout << "POS: ";
		for (int i = 0; i < num; ++i) {
			//cout << pos[i] << " ";
			//upd(tin[pos[i]], 1);
			//upd(tin[pos[(i + 1) % num]], 1);
			--cnt[tin[pos[i]] + 1];
			--cnt[tin[pos[i + 1]] + 1];
			int l = lca(pos[i], pos[i + 1]);
			//cout << "LCA: " << pos[i] << " " << pos[i + 1] << " " << l << "\n";
			cnt[tin[l] + 1] += 2;
		}
		//cout << "\n";
	}
	for (int i = 1; i < 2 * n; ++i) {
		cnt[i] += cnt[i - 1];
	}
	vector<int> ans;
	for (int i = 1; i < n; ++i) {
		//int num = qry(tin[i], tout[i]);
		int num = cnt[tin[i]] - cnt[tout[i]];
		//cout << num << "\n";
		if (num >= 2 * k) {
			ans.push_back(id[i]);
		}
	}
	sort(ans.begin(), ans.end());
	cout << ans.size() << "\n";
	for (int i : ans) {
		cout << i << " ";
	}
	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