Submission #684653

#	Time	Username	Problem	Language	Result	Execution time	Memory
684653		matu	Railway (BOI17_railway)	C++14	100 / 100	197 ms	26032 KiB

railway

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int n, m, k, cnt;
vector<pair<int, int>> g[N];
int up[N][20], tin[N], tout[N], mars[N];
int t[N];
bool cmp(int u, int v){
	return tin[u] < tin[v];
}
void dfs(int nod = 1, int p = 1){
	tin[nod] = ++cnt;
	up[nod][0] = p;

	for(int i = 1; i < 20; i++){
		up[nod][i] = up[up[nod][i - 1]][i - 1];
	}
	for(auto i : g[nod]){
		if(i.first != p){
			dfs(i.first, nod);
			t[i.first] = i.second;
		}
	}
	tout[nod] = ++cnt;
}	
bool is_ancestor(int u, int v){
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
	if(is_ancestor(u, v)) return u;
	if(is_ancestor(v, u)) return v;

	for(int i = 19; i >= 0; i--){
		if(!is_ancestor(up[u][i], v)){
			u = up[u][i];
		}
	}
	return up[u][0];
}

void dfs1(int nod = 1, int p = 1){
	//cout << nod << " " << p << '\n';
	for(auto i : g[nod]){
		if(i.first != p){
			dfs1(i.first, nod);
			mars[nod] += mars[i.first];
			
		}
	}
}
int main(){
	
	cin >> n >> m >> k;
	for(int i = 1; i < n; i++){
		int u, v;
		cin >> u >> v;
		g[u].push_back({v, i});
		g[v].push_back({u, i});
	}
	dfs();
	for(int i = 1; i <= m; i++){
		int t;
		cin >> t;
		vector<int> s(t + 10);
		for(int i = 1; i <= t; i++){
			cin >> s[i];
		}
		sort(s.begin() + 1, s.begin() + 1 + t, cmp);
		s[t + 1] = s[1];

		for(int i = 1; i <= t; i++){
			int lc = lca(s[i], s[i + 1]);
			mars[s[i]]++;
			mars[s[i + 1]]++;
			mars[lc]-=2;	
		}
		
	}
	dfs1();
	vector<int> sol;
	for(int i = 2; i <= n; i++){
		if(mars[i] >= 2 * k){
			sol.push_back(t[i]);
		}
	
	}
	cout << sol.size() << '\n';
	sort(sol.begin(), sol.end());
	for(auto i : sol) cout << i << " ";
}

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