Submission #1083940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083940		EkinOnal	Railway (BOI17_railway)	C++17	100 / 100	94 ms	30568 KiB

railway

//#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define MAX 100007
#define pb push_back
#define mp make_pair 
//#define int long long
#define f first
#define s second
#define vi vector<int>
#define pii pair<int,int>
#define si set<int>
#define vpii vector<pair<int,int>> 
const int mod = 1e9+7;
//const int INF = 1e18;
// myMap.begin()->first :  key
// myMap.begin()->second : value
 
int epow(int a,int b){int ans=1;while(b){if(b&1) ans*=a;a*=a;b>>=1;ans%=mod;a%=mod;}return (ans+mod)%mod;}
int gcd(int a,int b) {if(a<b)swap(a,b);while(b){int tmp=b;b=a%b;a=tmp;}return a;}
int mul(int a,int b){return ((a%mod)*(b%mod))%mod;}
int sum(int a,int b){return ((a%mod)+(b%mod))%mod;}

typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

vi dep(MAX),tin(MAX),tout(MAX),pare(MAX);
vpii adj[MAX];
vector<vi> p(MAX,vi(22));
int timer=0;
void tour(int node,int par){
	tin[node]=timer++;
	dep[node]=dep[par]+1;
	p[node][0]=par;
	for(auto u : adj[node]){
		if(u.f==par) continue;
		pare[u.f]=u.s;
		tour(u.f,node);
	}
	tout[node]=timer-1;
}

int find_lca(int a,int b){
	if(dep[a]<dep[b]) swap(a,b);
	int fark=dep[a]-dep[b];
	for(int i=20;i>=0;i--){
		if((1LL<<i)<=fark){
			fark-=(1LL<<i);
			a=p[a][i];
		}
	}
	if(a==b) return a;
	for(int i=20;i>=0;i--){
		if(p[a][i]!=p[b][i]){
			a=p[a][i];
			b=p[b][i];
		}
	}
	return p[a][0];
}

vi val(MAX),ans;
int n,m,k;
void dfs(int node,int par){
	for(auto u : adj[node]){
		if(u.f==par) continue;
		dfs(u.f,node);
		val[node]+=val[u.f];
	}
	if(val[node]>=2*k) ans.pb(pare[node]);
}

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

	tour(1,1);
	for(int i=1;i<=20;i++){
		for(int node=1;node<=n;node++) p[node][i]=p[p[node][i-1]][i-1];
	}
	
	while(m--){
		int s; cin>>s;
		vi v(s); for(int i=0;i<s;i++) cin>>v[i];
		sort(v.begin(),v.end(),[&](int a,int b)-> bool {
			return tin[a]<tin[b];
		});

		v.pb(v[0]);
		for(int i=0;i<s;i++){
			val[v[i]]++;
			val[v[i+1]]++;
			val[find_lca(v[i],v[i+1])]-=2;
		}
	}
	dfs(1,1);
	sort(ans.begin(),ans.end());
	cout<<ans.size()<<endl;
	for(auto u : ans) cout<<u<<" ";

	return;
}

int32_t main() {
//	freopen("in.in", "r", stdin);
//	freopen("out.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(0);   
    int t=1;
//    cin >> t;
    while (t--) solve();
 
    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