Submission #1197263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197263		Sofiatpc	Railway (BOI17_railway)	C++20	23 / 100	1097 ms	29660 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define fi first
#define sc second
const int MAXN = 1e5+5;
vector<int> adj[MAXN], id[MAXN];
int pai[MAXN], pid[MAXN], freq[MAXN];
map<int,int> mp[MAXN];

void marca(int a, int b, int c){
	int cur = a;
	while(cur != c){
		freq[pid[cur]]++;
		cur = pai[cur];
	}
	cur = b;
	while(cur != c){
		freq[pid[cur]]++;
		cur = pai[cur];
	}
}

void merge(int p , int f){
	if(sz(mp[p]) > sz(mp[f])){
		for(auto it : mp[f]){
			if(mp[p].find(it.fi) == mp[p].end()) mp[p][it.fi] = it.sc;
			else{
				marca(it.sc, mp[p][it.fi], p);
				mp[p][it.fi] = p;
			}
		}
	}
	else{
		for(auto it : mp[p]){
			if(mp[f].find(it.fi) == mp[f].end()) mp[f][it.fi] = it.sc;
			else{
				marca(it.sc, mp[f][it.fi], p);
				mp[f][it.fi] = p;
			}
		}
		swap(mp[f],mp[p]);
	}
	mp[f].clear();
}

void dfs(int s){
	for(int i = 0; i < sz(adj[s]); i++){
		int viz = adj[s][i];

		if(viz != pai[s]){
			pai[viz] = s;
			pid[viz] = id[s][i];

			dfs(viz);
			merge(s,viz);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n,m,k; cin>>n>>m>>k;
	for(int i = 1; i < n; i++){
		int a,b; cin>>a>>b;
		adj[a].push_back(b); id[a].push_back(i);
		adj[b].push_back(a); id[b].push_back(i);
	}

	for(int i = 1; i <= m; i++){
		int s; cin>>s;
		for(int j = 1; j <= s; j++){
			int v; cin>>v;
			mp[v][i] = v;
		}
	}

	dfs(1);

	int ans = 0;
	for(int i = 1; i < n; i++)
		if(freq[i] >= k)ans++;

	cout<<ans<<"\n";
	for(int i = 1; i < n; i++)
		if(freq[i] >= k)cout<<i<<" ";
	cout<<"\n";
}

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