Submission #230894

#	Time	Username	Problem	Language	Result	Execution time	Memory
230894		eohomegrownapps	Railway (BOI17_railway)	C++14	100 / 100	241 ms	45048 KiB

railway

#include <bits/stdc++.h>
using namespace std;
 
vector<vector<pair<int,int>>> adjlist;
vector<int> depth;
vector<set<int>*> sets;
vector<vector<int>> nadd;
vector<vector<int>> nremove;
vector<int> ans;
int pk[100000][20];
int n,k;
 
void dfs(int node, int parent){
	for (auto p : adjlist[node]){
		if (p.first==parent){continue;}
		int i=p.first;
		pk[i][0]=node;
		depth[i]=depth[node]+1;
		dfs(i,node);
	}
}
 
void decom2k(){
	for (int i = 1; i<20; i++){
		for (int j = 0; j<n; j++){
			if (pk[j][i-1]!=-1){
				pk[j][i]=pk[pk[j][i-1]][i-1];
			}
		}
	}
}
 
int lca(int a, int b){
	//wlog a deeper
	if (depth[b]>depth[a]){
		swap(a,b);
	}
	for (int i = 19; i>=0; i--){
		if (pk[a][i]==-1){continue;}
		if (depth[pk[a][i]]>=depth[b]){
			a=pk[a][i];
		}
	}
	if (a==b){
		return a;
	}
	for (int i = 19; i>=0; i--){
		if (pk[a][i]==-1){continue;}
		if (pk[a][i]!=pk[b][i]){
			a=pk[a][i];b=pk[b][i];
		}
	}
	return pk[a][0];
}
 
void setdfs(int node, int parent){
	if (parent!=-1&&adjlist[node].size()==1&&adjlist[node][0].first==parent){
		sets[node] = new set<int>();
		for (int i : nadd[node]){
			sets[node]->insert(i);
		}
		for (int i : nremove[node]){
			sets[node]->erase(i);
		}
		return;
	}
	int largestset = -1;
	int largestnode = -1;
	for (auto p : adjlist[node]){
		if (p.first==parent){continue;}
		setdfs(p.first,node);
		int s = sets[p.first]->size();
		if (s>=k){
			ans.push_back(p.second);
		}
		if (s>largestset){
			largestnode=p.first;
			largestset=s;
		}
	}
	for (auto p : adjlist[node]){
		if (p.first==parent){continue;}
		if (p.first==largestnode){continue;}
		sets[largestnode]->insert(sets[p.first]->begin(), sets[p.first]->end());
	}
	sets[node]=sets[largestnode];
	for (int i : nadd[node]){
		sets[node]->insert(i);
	}
	for (int i : nremove[node]){
		sets[node]->erase(i);
	}
}
 
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int m;
	cin>>n>>m>>k;
	adjlist.resize(n);
	depth.resize(n,0);
	nadd.resize(n);
	nremove.resize(n);
	sets.resize(n);
	for (int i = 0; i<n-1; i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		adjlist[a].push_back({b,i});
		adjlist[b].push_back({a,i});
	}
	pk[0][0]=-1;
	dfs(0,-1);
	decom2k();
	for (int i = 0; i<m; i++){
		int num;
		cin>>num;
		int prevlca = -1;
		for (int j = 0; j<num; j++){
			int x;
			cin>>x;
			x--;
			nadd[x].push_back(i);
			if (prevlca==-1){
				prevlca=x;
			} else {
				prevlca=lca(prevlca,x);
			}
		}
		//cout<<prevlca<<endl;
		nremove[prevlca].push_back(i);
	}
	setdfs(0,-1);
	sort(ans.begin(),ans.end());
	cout<<ans.size()<<'\n';
	for (int i : ans){
		cout<<i+1<<" ";
	}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