Submission #948830

#	Time	Username	Problem	Language	Result	Execution time	Memory
948830		koukirocks	Railway (BOI17_railway)	C++17	100 / 100	100 ms	28564 KiB

railway

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
 
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=1e5+10,P=998244353;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;

int n,m,k;
vector<pii> G[MAX];
vector<int> sel[MAX];
int BIT[MAX*2];

void update(int x,int val) {
	while (x<MAX*2) {
		BIT[x]+=val;
		x+=(-x&x);
	}
}

int query(int x) {
	ll ans=0;
	while (x) {
		ans+=BIT[x];
		x-=(-x&x);
	}
	return ans;
}

int tme=1;
int in[MAX],out[MAX];
int up[MAX][20];
int dep[MAX];

void dfs(int v,int p) {
	dep[v]=dep[p]+1;
	up[v][0]=p;
	for (int i=1;i<20;i++) up[v][i]=up[up[v][i-1]][i-1];
	in[v]=tme++;
	for (auto [i,w]:G[v]) {
		if (i==p) continue;
		dfs(i,v);
	}
	out[v]=tme++;
}

int lca(int a,int b) {
	if (dep[a]<dep[b]) swap(a,b);
	int mv=dep[a]-dep[b];
	for (int i=0;i<20;i++) {
		if (mv&(1<<i)) a=up[a][i];
	}
	if (a==b) return a;
	for (int i=19;i>=0;i--) {
		if (up[a][i]!=up[b][i]) {
			a=up[a][i];
			b=up[b][i];
		}
	}
	return up[a][0];
}

void pth(int a,int b) {
	int ans=lca(a,b);
//	cout<<a<<" "<<b<<" "<<ans<<" abans\n"<<flush;
	update(in[a],1);
	update(in[b],1);
	update(in[ans],-2);
}

void dfs2(int v,int p,int id,vector<int>& ans) {
	if (v!=1 and query(out[v])-query(in[v]-1)>=2*k) ans.push_back(id);
	for (auto [i,w]:G[v]) {
		if (i==p) continue;
		dfs2(i,v,w,ans);
	}
}

int main() {
	speed;
	cin>>n>>m>>k;
	for (int i=1;i<n;i++) {
		int a,b;
		cin>>a>>b;
		G[a].emplace_back(b,i);
		G[b].emplace_back(a,i);
	}
	dep[1]=0;
	dfs(1,1);
//	for (int i=1;i<=n;i++) {
//		cout<<in[i]<<" "<<out[i]<<" inout\n";
//	}
	memset(BIT,0,sizeof(BIT));
	for (int i=1;i<=m;i++) {
//		cout<<i<<"\n"<<flush;
		int s;
		cin>>s;
		for (int j=0;j<s;j++) {
			int x;
			cin>>x;
			sel[i].push_back(x);
		}
		if (s<=1) continue;
		sort(all(sel[i]),[=](int a,int b) {
			return in[a]<in[b];
		});
		for (int j=0;j<s;j++) {
			pth(sel[i][j],sel[i][(j+1)%s]);
		}
//		for (int i=1;i<=n;i++) {
//			cout<<query(out[i])-query(in[i]-1)<<" ";
//		}
//		cout<<"\n";
	}
//	cout<<"sgfhfh\n"<<flush;
	vector<int> ans;
	dfs2(1,1,0,ans);
//	for (int i=1;i<=n;i++) {
//		cout<<query(out[i])-query(in[i]-1)<<" ";
//	}
//	cout<<"\n";
	cout<<ans.size()<<"\n";
	sort(all(ans));
	for (int i:ans) cout<<i<<" ";
	cout<<"\n";
	return 0;
}


/*
6 3 2
1 3
2 3
3 4
6 4
4 5
4 1 3 2 5
2 6 3
2 3 2
*/

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