Submission #1306171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306171		Robert_junior	Railway (BOI17_railway)	C++20	23 / 100	1096 ms	16860 KiB

railway

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define all(x) x.begin(), x.end()
#define ins insert
#define pb push_back
#define F first
#define S second
#define bt bitset<5010>
const int N = 1e5 + 100, K = 1610;
const int mod = 998244353;
vector<pair<int, int>>g[N];
int sz[N];
int cnt[N];
int n, m, k, z;
void dfs(int v, int p){
	for(auto [to, idx] : g[v]){
		if(to == p) continue;
		dfs(to, v);
		if(sz[to] != z && sz[to] != 0) cnt[idx]++;
		sz[v] += sz[to];
	}
}
void solve(){
	cin>>n>>m>>k;
	for(int i = 1; i <= n - 1; i++){
		int u, v;
		cin>>u>>v;
		g[u].pb({v, i});
		g[v].pb({u, i});
	}
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= n; j++){
			sz[j] = 0;
		}
		cin>>z;
		for(int j = 1; j <= z; j++){
			int x; 
			cin>>x;
			sz[x] = 1; 
		}
		dfs(1, 1);
	}
	vector<int>ans;
	for(int i = 1; i <= n - 1; i++){
		if(cnt[i] >= k) ans.pb(i);
	}
	cout<<ans.size()<<'\n';
	for(auto it : ans){
		cout<<it<<' ';
	}
}
main(){
	ios_base :: sync_with_stdio(false); 
	cin.tie(nullptr);
	int t = 1;
	//cin>>t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

railway.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main(){
      | ^~~~

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