Submission #1042989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042989		pacman	Railway (BOI17_railway)	C++17	100 / 100	154 ms	42700 KiB

railway

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 100, lg = 30;

int n ,m ,k, st[maxn], fn[maxn], cnt , par[lg][maxn], h[maxn], dp[maxn];

vector<int> adj[maxn];
map<pair<int, int>, int> mapi;
vector<pair<int, int>> q;
vector<int> ans;


void dfs(int v ,int mpar = 0){
	st[v] = cnt++;
	par[0][v] = mpar;
	
	for(int i = 1 ; i < lg ; i++){
		par[i][v] = par[i - 1][par[i - 1][v]];
	}
	
	for(auto u : adj[v]){
		if(u != mpar){
			h[u] = h[v] + 1;
			dfs(u, v);
		}
	}
	fn[v] = cnt++;
}


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


void check(int v ,int mpar = 0){
	for(auto u : adj[v]){
		if(u != mpar){
			check(u, v);
		}
	}
	
	dp[mpar] += dp[v];
	
	if(dp[v] >= (2 * k) and mapi[{v ,mpar}] != 0){
		ans.push_back(mapi[{v ,mpar}]);
	}
}


int main(){
	
	ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
	
	cin >> n >> m >> k;
	
	for(int i = 1 ;i < n; i++){
		int x ,y;
		cin >> x >> y;
		
		adj[x].push_back(y);
		adj[y].push_back(x);
		mapi[{x ,y}]= i;
		mapi[{y , x}]= i;
	}
	
	//h[1] = 1;
	dfs(1);
	
	while(m--){
		int x;
		cin >> x;
		q.push_back({0, 0});
		for(int i = 1 ; i <= x ; i++){
			int y;
			cin >> y;
			q.push_back({st[y], y});
		}
		
		sort(q.begin(), q.end());
		
		for(int i = 2 ; i <= x ; i++){
			dp[q[i - 1].second]++;
			dp[q[i].second]++;
			dp[lca(q[i].second, q[i - 1].second)] -= 2;
		}
		
		dp[q[1].second]++;
		dp[q[x].second]++;
		dp[lca(q[x].second, q[1].second)] -= 2;
		
		q.clear();
	}

	check(1);
	
	sort(ans.begin(), ans.end());
	
	cout << ans.size() << endl;
	for(auto i : ans){
		cout << i << ' ';
	}
	cout << endl;
	
	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