Submission #331479

#	Time	Username	Problem	Language	Result	Execution time	Memory
331479		rqi	Railway (BOI17_railway)	C++14	100 / 100	192 ms	27620 KiB

railway

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define f first
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define mp make_pair

const int mx = 100005;

int n, m, k;
int a[mx];
int b[mx];
vpi adj[mx];
vpi s[mx];
int etind[mx];
int edgeind[mx];
int curetind = 0;

void genET(int node, int prv = -1){
	etind[node] = ++curetind;
	for(auto u: adj[node]){
		if(u.f == prv) continue;
		genET(u.f, node);
		edgeind[u.f] = u.s;
	}
}

vi queries[mx];
int sum[mx];

vi ances;
vi e;

int get(int a){
	if(e[a] < 0) return a;
	e[a] = get(e[a]);
	return e[a];
}

bool unite(int a, int b){
	a = get(a);
	b = get(b);
	if(a == b) return 0;
	if(-e[a] < -e[b]) swap(a, b);
	e[a]+=e[b];
	e[b] = a;
	if(etind[ances[a]] > etind[ances[b]]){
		ances[a] = ances[b];
	}
	return 1;
}

void genLCA(int node, int prv = -1){
	for(auto u: queries[node]){
		sum[ances[get(u)]]-=2;
	}
	for(auto u: adj[node]){
		if(u.f == prv) continue;
		genLCA(u.f, node);
		unite(u.f, node);
	}
}

void genSums(int node, int prv = -1){
	for(auto u: adj[node]){
		if(u.f == prv) continue;
		genSums(u.f, node);
		sum[node]+=sum[u.f];
	}
}

int main(){
	int n, m, k;
	cin >> n >> m >> k;

	ances = e = vi(n+5, -1);
	for(int i = 1; i <= n; i++){
		ances[i] = i;
	}

	for(int i = 1; i <= n-1; i++){
		cin >> a[i] >> b[i];
		adj[a[i]].pb(mp(b[i], i));
		adj[b[i]].pb(mp(a[i], i));
	}

	genET(1);

	for(int i = 1; i <= m; i++){
		int num;
		cin >> num;
		for(int j = 0; j < num; j++){
			int x;
			cin >> x;
			s[i].pb(mp(etind[x], x));
		}
		sort(all(s[i]));
		s[i].pb(s[i][0]);
	}

	for(int i = 1; i <= m; i++){
		for(int j = 0; j < sz(s[i])-1; j++){
			int a = s[i][j].s;
			int b = s[i][j+1].s;
			if(etind[a] > etind[b]) swap(a, b);
			queries[b].pb(a);
			sum[a]++;
			sum[b]++;
		}
	}

	genLCA(1);
	genSums(1);

	vi ans;
	for(int i = 2; i <= n; i++){
		if(sum[i]/2 >= k){
			ans.pb(edgeind[i]);
		}
	}
	sort(all(ans));
	cout << sz(ans) << "\n";
	for(auto u: ans){
		cout << u << " ";
	}
	cout << "\n";

}

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