Submission #1091895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091895		4QT0R	Railway (BOI17_railway)	C++17	100 / 100	95 ms	35136 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define ll long long

vector<pair<ll,ll>> graph[100003];
ll preorder[100003];
ll postorder[100003];
ll iter=0;
ll jmp[100003][19];
ll dep[100003];

ll sum[100003];

void dfs(ll v, ll p){
	preorder[v]=iter++;
	jmp[v][0]=p;
	for (ll i = 1; i<19; i++)jmp[v][i]=jmp[jmp[v][i-1]][i-1];
	for (auto [u,ind] : graph[v]){
		if (u==p)continue;
		dep[u]=dep[v]+1;
		dfs(u,v);
	}
	postorder[v]=iter++;
}

ll lca(ll a, ll b){
	if (dep[a]<dep[b])swap(a,b);
	for (ll i = 18; i>=0; i--)if (dep[jmp[a][i]]>=dep[b])a=jmp[a][i];
	if (a==b)return a;
	for (ll i = 18; i>=0; i--)if (jmp[a][i]!=jmp[b][i]){
		a=jmp[a][i];
		b=jmp[b][i];
	}
	return jmp[a][0];
}

vector<ll> ans;
void dfs2(ll v, ll p){
	for (auto [u,ind] : graph[v]){
		if (u==p)continue;
		dfs2(u,v);
		sum[v]+=sum[u];
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	ll n,m,k;
	cin >> n >> m >> k;
	for (ll i = 1,v,u; i<n; i++){
		cin >> v >> u;
		graph[v].push_back({u,i});
		graph[u].push_back({v,i});
	}
	dfs(1,1);
	for (ll i = 1,s; i<=m; i++){
		cin >> s;
		vector<ll> vec(s);
		for (ll j = 0; j<s; j++)cin >> vec[j];
		sort(vec.begin(),vec.end(),[](ll a, ll b){return preorder[a]<preorder[b];});
		vec.push_back(vec[0]);
		for (ll j = 0; j<s; j++){
			sum[vec[j]]++;
			sum[vec[j+1]]++;
			sum[lca(vec[j],vec[j+1])]-=2;
		}
	}
	dfs2(1,0);
	for (ll v = 1; v<=n; v++){
		for (auto [u,ind] : graph[v]){
			if (preorder[u]<preorder[v] && postorder[u]>postorder[v] && sum[v]>=2*k){
				ans.push_back(ind);
			}
		}
	}
	sort(ans.begin(),ans.end());
	cout << ans.size() << '\n';
	for (auto u : ans)cout << u << ' ';
	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