Submission #378269

#	Time	Username	Problem	Language	Result	Execution time	Memory
378269		negar_a	Railway (BOI17_railway)	C++14	100 / 100	307 ms	45460 KiB

railway

//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 1e5 + 5, lg = 19;
vector <pii> adj[maxn];
vector <int> del[maxn];
vector <int> ans;
set <int> st[maxn];

int par[maxn][lg + 5], h[maxn];
int n, m, k;

void dfs(int v){
	for(auto x : adj[v]){
		int u = x.F;
		if(u != par[v][0]){
			h[u] = h[v] + 1;
			par[u][0] = v;
			for(int i = 1; i < lg; i ++){
				par[u][i] = par[par[u][i - 1]][i - 1];
			}
			dfs(u);
		}
	}
}

int get_par(int x, int p){
	for(int i = 0; i < lg; i ++){
		if(p & (1 << i)){
			x = par[x][i];
		}
	}
	return x;
}

int lca(int x, int y){
	if(h[x] < h[y]){
		swap(x, y);
	}
	x = get_par(x, h[x] - h[y]);
	for(int i = lg; i >= 0; i --){
		if(par[x][i] != par[y][i]){
			x = par[x][i];
			y = par[y][i];
		}
	}
	if(x == y)
		return x;
	return par[x][0];
}

inline void merge(int u, int v){
	if(st[u].size() < st[v].size()){
		swap(st[u], st[v]);
	}
	for(int x : st[v]){
		st[u].insert(x);
	}
}

void sfd(int v){
	for(auto u : adj[v]){
		if(u.F != par[v][0]){
			sfd(u.F);
			if(st[u.F].size() >= k){
				ans.pb(u.S + 1);
			}
			merge(v, u.F);
		}
	}
	for(int x : del[v]){
		st[v].erase(x);
	}
}

int main(){
	fast_io;
	
	cin >> n >> m >> k;
	for(int i = 0; i < n - 1; i ++){
		int x, y;
		cin >> x >> y;
		x --; y --;
		adj[x].pb({y, i});
		adj[y].pb({x, i});
	}
	dfs(0);
	for(int i = 0; i < m; i ++){
		int s;
		cin >> s;
		int x; cin >> x; x --;
		st[x].insert(i);
		int lc = x;
		for(int j = 0; j < s - 1; j ++){
			cin >> x;
			x --;
			lc = lca(lc, x);
			st[x].insert(i);
		}
		del[lc].pb(i);
	}
	sfd(0);
	
	cout << ans.size() << endl;
	sort(ans.begin(), ans.end());
	for(int u : ans){
		cout << u << " ";
	}
	
	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void sfd(int)':
railway.cpp:75:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |    if(st[u.F].size() >= k){
      |       ~~~~~~~~~~~~~~~^~~~

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