Submission #1128572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128572		Muhammet	Railway (BOI17_railway)	C++20	100 / 100	204 ms	53704 KiB

railway

#include "bits/stdc++.h"

using namespace std;

#define SZ(s) (int)s.size()

const int N = 1e5+5;

int n, m, k;

set <int> s[N];

vector <int> p, h, c;

vector <vector <int>> v, sp, v1;

map <pair<int,int>, int> mp;

void dfs(int x, int y = 0){
	for(auto i : v[x]){
		if(i == y) continue;
		h[i] = h[x]+1;
		p[i] = x;
		dfs(i,x);
	}
}

void df(int x, int y = 0){
	for(auto i : v[x]){
		if(i == y) continue;
		df(i,x);
		if(SZ(s[x]) < SZ(s[i])) swap(s[x], s[i]);
		while(SZ(s[i]) > 0){
			s[x].insert(*s[i].begin());
			s[i].erase(s[i].begin());
		}
	}
	while(SZ(v1[x]) > 0){
		s[x].erase(s[x].find(v1[x].back()));
		v1[x].pop_back();
	}
	if(SZ(s[x]) >= k) mp[{min(x,y), max(x,y)}] = 1;
	return;
}

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

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> m >> k;
	v.resize(n+1), v1.resize(n+1);
	sp.assign(n+1, vector <int> (25,0));
	p.assign(n+1,0), h.assign(n+1,0), c.assign(n+1,0);
	vector <int> u1(n+1), u2(n+1);
	for(int i = 1; i < n; i++){
		cin >> u1[i] >> u2[i];
		v[u1[i]].push_back(u2[i]);
		v[u2[i]].push_back(u1[i]);
	}
	h[1] = 1;
	dfs(1);
	for(int i = 1; i <= n; i++){
		sp[i][0] = p[i];
	}
	for(int j = 1; j <= 20; j++){
		for(int i = 1; i <= n; i++){
			sp[i][j] = sp[sp[i][j-1]][j-1];
		}
	}
	vector <int> a;
	for(int i = 1; i <= m; i++){
		int s1;
		cin >> s1;
		a.clear();
		for(int j = 1; j <= s1; j++){
			int x;
			cin >> x;
			a.push_back(x);
			s[x].insert(i);
		}
		int lc = a[0];
		for(int j = 1; j < s1; j++){
			lc = lca(a[j], lc);
		}
		v1[lc].push_back(i);
	}
	df(1);
	vector <int> v2;
	for(int i = 1; i < n; i++){
		if(mp[{min(u1[i], u2[i]), max(u1[i], u2[i])}] == true) v2.push_back(i);
	}
	cout << SZ(v2) << '\n';
	for(auto i : v2){
		cout << i << ' ';
	}
	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