Submission #1282960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282960		Jawad_Akbar_JJ	Railway (BOI17_railway)	C++20	100 / 100	214 ms	44476 KiB

railway

#include <iostream>
#include <vector>
#include <set>

using namespace std;
const int N = 1<<17;
vector<pair<int,int>> nei[N];
vector<int> ers[N];
set<int> st[N];
int hei[N], par[N][20], Ans[N], Sz, n, m, k;

void dfs(int u, int p){
	hei[u] = hei[p] + 1;
	par[u][0] = p;

	for (int i=1;i<17;i++)
		par[u][i] = par[par[u][i-1]][i-1];

	for (auto [i, ind] : nei[u]){
		if (i == p)
			continue;
		dfs(i, u);
	}
}

void moveUp(int &v, int d){
	for (int i=0;i<17;i++)
		if ((1<<i) & d)
			v = par[v][i];
}

int LCA(int u, int v){
	if (hei[u] > hei[v])
		swap(u, v);

	moveUp(v, hei[v] - hei[u]);
	if (u == v)
		return u;

	for (int i=16;i>=0;i--){
		if (par[u][i] != par[v][i])
			u = par[u][i], v = par[v][i];
	}
	return par[u][0];
}

void dfs2(int u, int p, int id = 0){
	for (auto [i, ind] : nei[u]){
		if (i == p)
			continue;
		dfs2(i, u, ind);

		if (st[i].size() > st[u].size())
			swap(st[u], st[i]);
		for (int j : st[i])
			st[u].insert(j);
	}
	for (int i : ers[u])
		st[u].erase(i);

	if (st[u].size() >= k)
		Sz++, Ans[id] = 1;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>>n>>m>>k;

	for (int i=1, a, b;i<n;i++){
		cin>>a>>b;
		nei[a].push_back({b, i});
		nei[b].push_back({a, i});
	}

	dfs(1, 0);

	for (int i=1, s, lca;i<=m;i++){
		cin>>s>>lca;
		st[lca].insert(i);

		for (int k=1, v;k<s;k++)
			cin>>v, lca = LCA(lca, v), st[v].insert(i);
		ers[lca].push_back(i);
	}

	dfs2(1, 0);

	cout<<Sz<<'\n';
	for (int i=1;i<n;i++){
		if (Ans[i])
			cout<<i<<' ';
	}
	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