Submission #718191

#	Time	Username	Problem	Language	Result	Execution time	Memory
718191		starplat	Railway (BOI17_railway)	C++14	100 / 100	259 ms	26136 KiB

railway

#include <bits/stdc++.h>
using namespace std;
int n,m,k,u,v,tin,diff[100005],s[100005];
int in[100005],out[100005],lift[25][100005];
vector<pair<int,int> > grh[100005];
bool is(int x,int y){
	return in[x]<=in[y] && out[x]>=out[y];
}

int lca(int x,int y){
	if (is(x,y)) return x;
	if (is(y,x)) return y;
	for (int i=20;i>=0;i--){
		if (lift[i][x] && !is(lift[i][x],y)){
			x=lift[i][x];
		}
	}	
	return lift[0][x];
}

void euler(int x,int p){
	in[x]=++tin; lift[0][x]=p;
	for (int i=1;i<=20;i++) {
		lift[i][x]=lift[i-1][lift[i-1][x]];
	}
	for (auto i:grh[x]) {
		if (i.first!=p) euler(i.first,x);
	}
	out[x]=++tin;
}

bool cp(int x,int y){
	return in[x]<in[y];
}
vector<int> ans;
void dfs(int x,int p){
	for (auto i:grh[x]){
		if (i.first!=p){
			dfs(i.first,x);
			diff[x]+=diff[i.first];
			if (diff[i.first]>=k) ans.push_back(i.second);
		}
	}
}
int main(){
	cin>>n>>m>>k;
	for (int i=1;i<n;i++){
		cin>>u>>v;
		grh[u].push_back({v,i});
		grh[v].push_back({u,i});
	}
	euler(1,0);
	in[n+1]=out[n+1]=INT_MAX;
	while (m--){
		int k; cin>>k;
		int anc=0;
		for (int i=1;i<=k;i++) {
			cin>>s[i];
			if (i==1) anc=s[i];
			else anc=lca(anc,s[i]);
		}
		s[k+1]=n+1;
		sort(s+1,s+1+k,cp);
		vector<int> imp,vt; set<pair<int,int> > implca;
		for (int i=1;i<=k;i++){
			if (out[s[i]]<in[s[i+1]]) {
				imp.push_back(s[i]);
				implca.insert({in[s[i]],s[i]});
				diff[s[i]]++;
			}
		}
		for (int i=1;i<imp.size();i++){
			int nde=lca(imp[i-1],imp[i]);
			if (nde!=anc) {
				implca.insert({in[nde],nde});
			}
		}
		for (auto it=implca.begin();it!=implca.end();it++) vt.push_back(it->second);
		sort(vt.begin(),vt.end(),cp); vt.push_back(n+1);
		for (int i=vt.size()-2;i>=0;i--){
			auto lt=implca.lower_bound({in[vt[i]]+1,-1});
			auto rt=implca.upper_bound({out[vt[i]],-1});
			vector<set<pair<int,int>>::iterator> tr;
			for (auto it=lt;it!=implca.end();it++){
				if (is(vt[i],it->second)) tr.push_back(it);
			}
			if (tr.empty()) continue;
			diff[vt[i]]=diff[vt[i]]-(int)tr.size()+1;
			//cout<<vt[i]<<" "<<tr.size()<<"\n";
			for (auto it:tr) implca.erase(it);
		}
		int cnt=implca.size();
	//	cout<<cnt<<"\n";
		diff[anc]-=cnt;
	}
	dfs(1,0);
//	for (int i=1;i<=n;i++) cout<<diff[i]<<" ";cout<<"\n";
	sort(ans.begin(),ans.end());
	cout<<ans.size()<<"\n";
	if (ans.empty()) return 0;
	cout<<ans[0];
	for (int i=1;i<ans.size();i++) cout<<" "<<ans[i];
	cout<<"\n";
}
/*
13 1 1
1 2
2 3
3 4
3 5
3 6
6 7
7 8
7 9
6 10
3 11
11 12
11 13
8 2 4 5 8 9 10 12 13
*/

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for (int i=1;i<imp.size();i++){
      |                ~^~~~~~~~~~~
railway.cpp:82:9: warning: variable 'rt' set but not used [-Wunused-but-set-variable]
   82 |    auto rt=implca.upper_bound({out[vt[i]],-1});
      |         ^~
railway.cpp:102:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for (int i=1;i<ans.size();i++) cout<<" "<<ans[i];
      |               ~^~~~~~~~~~~

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