Submission #884774

#	Time	Username	Problem	Language	Result	Execution time	Memory
884774		arashMLG	Railway (BOI17_railway)	C++17	100 / 100	90 ms	25036 KiB

railway

#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

typedef long long     ll;
typedef pair<int,int> pii;

const int N = 1e5 + 23;
const int LOG = 23;
const ll inf = 1e18;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)

int n,m,k;
vector<pii> G[N];
int dp[N];
int up[LOG][N];
int h[N];
int st[N],timer =0;

void dfsset(int v,int p = 1) {
	up[0][v] = p;
	st[v] = timer ++;
	for(int i = 1; i < LOG; i ++) {
		up[i][v] = up[i-1][up[i-1][v]];
	}
	for(auto [u,_] : G[v]) if(u != p) {
		h[u] = h[v] + 1;
		dfsset(u,v);
	}
}

int getPar(int v,int sex) {
	for(int i = 0 ;i < LOG ; i ++) 
		if((sex>>i)&1)
			v = up[i][v];
	return v;
}

int lca(int v,int u) {
	if(h[v] < h[u]) swap(v,u);
	v= getPar(v,h[v]-h[u]);
	if(v == u) return v;
	for(int i = LOG-1;i >=0 ; i --) 
		if(up[i][v] != up[i][u])
			v = up[i][v],u = up[i][u];
	return up[0][v];
}

vector<int> ans;

void dfs(int v,int p = -1,int wid=-1) {
	for(auto [u,_] : G[v]) if(u != p) {
		dfs(u,v,_);
		dp[v] += dp[u];
	}
	if(wid != -1 && dp[v]/2 >= k) {
		ans.pb(wid);
	}
}

vector<int> sex;

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>m>>k;
	for(int i =1; i < n ; i ++) {
		int v,u; cin>>v>>u;
		G[v].pb({u,i});
		G[u].pb({v,i});
	}
	dfsset(1);
	while(m--) {
		sex.clear();
		int s; cin>>s;
		for(int i = 0; i < s; i++) {
			int x; cin>>x;
			sex.pb(x);
		}
		sort(all(sex), [&] (int x,int y) {return st[x] < st[y];});
		for(int i = 1; i < s; i ++) {
			int v = sex[i-1],u =sex[i];
			dp[v] ++,dp[u] ++;
			dp[lca(v,u)] -= 2;
		}
		dp[sex[0]] ++,dp[sex[s-1]] ++;
		dp[lca(sex[0],sex[s-1])] -= 2;
	}
	dfs(1);
	sort(all(ans));
	cout<<sz(ans) << '\n';
	for(int x : ans) cout<<x << ' ';
	return 0;
}

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