Submission #714666

#	Time	Username	Problem	Language	Result	Execution time	Memory
714666		ajab_01	Railway (BOI17_railway)	C++17	100 / 100	185 ms	35668 KiB

railway

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

const int N = 1e5 + 5;
vector<pair<int , int> > g[N];
set<pair<int , int> > st[N];
vector<int> ans;
int sz[N] , n , m , k;

void dfs(int v , int par , int num){
	for(auto i : g[v]){
		int u = i.first , w = i.second;
		if(u == par) continue;
		dfs(u , v , w);
		if(st[v].size() < st[u].size())
			swap(st[v] , st[u]);
		for(auto &p : st[u]){
			auto it = st[v].lower_bound({p.first , -1});
			if(it == st[v].end()){
				st[v].insert(p);
				continue;
			}
			pair<int , int> pp = *it;
			if(pp.first == p.first){
				st[v].erase(pp);
				if(p.second + pp.second != sz[p.first])
					st[v].insert({p.first , p.second + pp.second});
			}
			else{
				st[v].insert(p);
			}
		}
		st[u].clear();
	}


	if((int)st[v].size() >= k)
		ans.push_back(num);
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 1 ; i <= n - 1 ; i++){
		int u , v;
		cin >> u >> v;
		g[u].push_back({v , i});
		g[v].push_back({u , i});
	}

	for(int i = 1 ; i <= m ; i++){
		int s;
		cin >> s;
		sz[i] = s;
		for(int j = 0 ; j < s ; j++){
			int x;
			cin >> x;
			if(s == 1) continue;
			st[x].insert({i , 1});
		}
	}

	dfs(1 , 0 , 0);

	sort(ans.begin() , ans.end());

	cout << (int)ans.size() << '\n';
	for(int i : ans)
		cout << i << ' ';
	cout << '\n'; 
	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