Submission #667157

#	Time	Username	Problem	Language	Result	Execution time	Memory
667157		flappybird	Railway (BOI17_railway)	C++17	100 / 100	198 ms	45020 KiB

railway

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 101010
#define MAXS 18
#define INF 10000000000000
#define bb ' '
#define ln '\n'
#define Ln '\n'
set<int> st[MAX];
vector<int> adj[MAX];
int psum[MAX];
pii edges[MAX];
int pedge[MAX];
int sp[MAX][MAXS];
int dep[MAX];
void dfs(int x) {
	int i;
	for (i = 1; i < MAXS; i++) sp[x][i] = sp[sp[x][i - 1]][i - 1];
	for (auto v : adj[x]) if (v != sp[x][0]) {
		sp[v][0] = x;
		dep[v] = dep[x] + 1;
		dfs(v);
	}
}
int lca(int u, int v) {
	if (!u) return v;
	if (!v) return u;
	int i;
	if (dep[u] != dep[v]) {
		if (dep[u] > dep[v]) swap(u, v);
		int d = dep[v] - dep[u];
		for (i = 0; i < MAXS; i++) if (d >> i & 1) v = sp[v][i];
	}
	if (u == v) return u;
	for (i = MAXS - 1; i >= 0; i--) if (sp[u][i] != sp[v][i]) u = sp[u][i], v = sp[v][i];
	return sp[u][0];
}
void calc(int x) {
	int sum = st[x].size();
	for (auto v : adj[x]) if (v != sp[x][0]) {
		calc(v);
		sum += st[v].size();
		if (st[v].size() > st[x].size()) st[v].swap(st[x]);
		for (auto a : st[v]) st[x].insert(a);
	}
	psum[x] -= (sum - st[x].size());
	for (auto v : adj[x]) if (v != sp[x][0]) psum[x] += psum[v];
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, K;
	cin >> N >> M >> K;
	int i, a, b;
	for (i = 1; i < N; i++) {
		cin >> a >> b;
		edges[i] = { a, b };
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dep[1] = 1;
	dfs(1);
	for (i = 1; i < N; i++) {
		tie(a, b) = edges[i];
		pedge[(sp[a][0] == b) ? a : b] = i;
	}
	int v;
	for (i = 1; i <= M; i++) {
		int s;
		cin >> s;
		int l = 0;
		vector<int> lst;
		while (s--) cin >> v, lst.push_back(v);
		sort(lst.begin(), lst.end());
		lst.erase(unique(lst.begin(), lst.end()), lst.end());
		if (lst.size() == 1) {
			K--;
			continue;
		}
		for (auto v : lst) {
			psum[v]++;
			st[v].insert(i);
			l = lca(v, l);
		}
		psum[l]--;
	}
	calc(1);
	vector<int> ansv;
	for (i = 1; i <= N; i++) if (psum[i] >= K) ansv.push_back(pedge[i]);
	sort(ansv.begin(), ansv.end());
	cout << ansv.size() << Ln;
	for (auto v : ansv) cout << v << bb;
}

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