Submission #1191136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191136		boclobanchat	Railway (BOI17_railway)	C++20	100 / 100	90 ms	23804 KiB

railway

#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN=1e5+5;
int e[MAXN],dp[MAXN],L[MAXN],R[MAXN],dis[MAXN],sp[MAXN][22],tdfs=0;
vector<ii> ds[MAXN];
bool comp(int a,int b) { return L[a]<L[b]; }
void dfs(int i,int pre)
{
	L[i]=++tdfs,sp[i][0]=pre;
	for(int j=1;j<=16;j++) sp[i][j]=sp[sp[i][j-1]][j-1];
	for(auto v:ds[i]) if(v.fi!=pre)
	{
		dis[v.fi]=dis[i]+1,e[v.fi]=v.se;
		dfs(v.fi,i);
	}
	R[i]=tdfs;
}
int lca(int a,int b)
{
	int x=dis[a],y=dis[b],m=min(x,y);
	for(int i=16;i+1;i--)
	{
		if((x-m)&(1<<i)) a=sp[a][i];
		if((y-m)&(1<<i)) b=sp[b][i];
	}
	if(a==b) return a;
	for(int i=16;i+1;i--) if(sp[a][i]!=sp[b][i]) a=sp[a][i],b=sp[b][i];
	return sp[a][0];
}
bool isancestor(int a,int b) { return L[a]<=L[b]&&R[b]<=R[a]; }
void virtualupdate(vector<int> vi)
{
	sort(vi.begin(),vi.end(),comp);
	int sz=vi.size();
	for(int i=0;i<sz-1;i++) vi.push_back(lca(vi[i],vi[i+1]));
	sort(vi.begin(),vi.end(),comp);
	vi.erase(unique(vi.begin(),vi.end()),vi.end());
	stack<int> st;
	for(auto v:vi)
	{
		while(!st.empty()&&!isancestor(st.top(),v)) st.pop();
		if(!st.empty()) dp[v]++,dp[st.top()]--;
		st.push(v);
	}
}
void dfsus(int i,int pre)
{
	for(auto v:ds[i]) if(v.fi!=pre)
	{
		dfsus(v.fi,i);
		dp[i]+=dp[v.fi];
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<n;i++)
	{
		int l,r;
		cin>>l>>r;
		ds[l].push_back({r,i}),ds[r].push_back({l,i});
	}
	dfs(1,1);
	while(m--)
	{
		int k;
		cin>>k;
		vector<int> vi;
		while(k--)
		{
			int res;
			cin>>res;
			vi.push_back(res);
		}
		virtualupdate(vi);
	}
	dfsus(1,1);
	vector<int> ans;
	for(int i=2;i<=n;i++) if(dp[i]>=k) ans.push_back(e[i]);
	sort(ans.begin(),ans.end());
	cout<<ans.size()<<"\n";
	for(auto v:ans) cout<<v<<" ";
}

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