제출 #1311238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311238		neonglitch	Railway (BOI17_railway)	C++20	100 / 100	75 ms	22248 KiB

railway

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
const int N=1e5+10,LG=18;
vector<pair<int,int>> ma[N];
int par[N][LG],h[N],sm[N],tmp=0,tin[N],tout[N],edg[N];
void dfs(int x,int p=0)
{
	h[x]=h[p]+1;
	par[x][0]=p;
	for(int j=1;j<LG;j++)par[x][j]=par[par[x][j-1]][j-1];
	tin[x]=tmp++;
	for(auto [y,id]:ma[x])
	{
		if(y^p)
			edg[y]=id,dfs(y,x);
	}
	tout[x]=tmp;
}
int lca(int x,int y)
{
	if(h[x]>h[y])swap(x,y);
	for(int j=LG-1;j>=0;j--)
	{
		if(h[par[y][j]]>=h[x])
		{
			y=par[y][j];
		}
	}
	if(x==y)return x;
	for(int j=LG-1;j>=0;j--)
	{
		if(par[x][j]!=par[y][j])
		{
			x=par[x][j];
			y=par[y][j];
		}
	}
	return par[x][0];
}
bool bytin(int x,int y){
	return tin[x]<tin[y];
}
void dfs(int x,vector<int>&pos)
{
	while(pos.size()>0 and tout[pos.back()]<=tout[x])
	{
		int y=pos.back();
		pos.pop_back();
		sm[y]++;
		sm[x]--;
		//<<"Add to path "<<x<<' '<<y<<endl;
		dfs(y,pos);
	}
}
void dfs_(int x,int p=0)
{
	//<<"At "<<x<<' '<<sm[x]<<endl;
	for(auto [y,id]:ma[x])
	{
		if(y^p)
			dfs_(y,x),sm[x]+=sm[y];
	}
	//<<"fnl "<<x<<' '<<sm[x]<<endl;
}
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 x,y;
		cin>>x>>y;
		ma[x].push_back({y,i});
		ma[y].push_back({x,i});
	}
	dfs(1);
	for(int i=0;i<m;i++)
	{
		int sz;
		cin>>sz;
		vector<int> cur;
		for(int j=0;j<sz;j++)
		{
			int x;
			cin>>x;
			cur.push_back(x);
		}
		sort(begin(cur),end(cur),bytin);
		set<int> nodes(begin(cur),end(cur));
		for(int j=0;j<sz;j++)
		{
			int x=lca(cur[j],cur[(j+1)%sz]);
			nodes.insert(x);
		}
		cur.clear();
		for(auto x:nodes)cur.push_back(x);
		sort(begin(cur),end(cur),bytin);
		reverse(begin(cur),end(cur));
		int rt=cur.back();
		cur.pop_back();
		dfs(rt,cur);
	}
	dfs_(1);
	vector<int> ans;
	for(int i=2;i<=n;i++)
	{
		if(sm[i]>=k)ans.push_back(edg[i]);
	}
	sort(begin(ans),end(ans));
	cout<<ans.size()<<endl;
	for(auto x:ans)cout<<x<<' ';
	cout<<endl;
}

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