Submission #823563

#	Time	Username	Problem	Language	Result	Execution time	Memory
823563		beaboss	Railway (BOI17_railway)	C++14	100 / 100	74 ms	23768 KiB

railway

// Source: https://oj.uz/problem/view/BOI17_railway
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

const int N = 1e5 + 10;

vi adj[N];

int tin[N];
int tout[N];
int dep[N];
int bit[N];

int query_pref(int ind) {
	int ret = 0;
    for (; ind >= 0; ind = (ind & (ind + 1)) - 1)
        ret += bit[ind];
    return ret;
}

int query(int ind1, int ind2) {
	return query_pref(ind2 - 1) - query_pref(ind1-1);
}

void update(int ind, int val) {
	for (; ind < N; ind = ind | (ind + 1))
            bit[ind] += val;
}

int lift[N][20];

int timer = 0;

void dfs(int cur, int p) {
	tin[cur]=timer++;
	lift[cur][0]=p;
	dep[cur] = dep[p] + 1;
	for (auto val: adj[cur]) if (val != p) dfs(val, cur);

	tout[cur]=timer;
}

int jmp(int a, int d) {
	// cout << ' ' << a << d << endl;
	for (int i = 19; i>= 0; i--) if ((1 << i) & d) a = lift[a][i];
	// cout << a << endl;
	return a;
}

int LCA(int a, int b) {
	if (dep[b] > dep[a]) swap(a, b); // a is lower
	// cout << a << b << dep[a] << dep[b] << endl;
	a = jmp(a, dep[a]-dep[b]);
	// cout << a << b << endl;
	if (a==b)return a;

	for (int i = 19; i>= 0; i--)
		if (lift[a][i] != lift[b][i]) {
			a = lift[a][i];
			b = lift[b][i];
		}

	assert(lift[a][0] == lift[b][0]);
	return lift[a][0];

}



pii edges[N];

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

	int n, m, k;
	cin >> n >> m >> k;


	FOR(i, 0, n-1) {
		int a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
		edges[i]={a, b};
	}

	dfs(1, 0);

	FOR(j, 1, 20) FOR(i, 1, n + 1) lift[i][j] = lift[lift[i][j-1]][j-1];



	int s;

	FOR(i, 0, m) {
		cin >> s;
		int cur[s+1];
		FOR(j, 0, s) 
			cin >> cur[j];

		sort(cur, cur + s, [&](int a, int b) {return tin[a] < tin[b]; });

		cur[s] = cur[0];

		FOR(i, 0, s) {
			int lca = LCA(cur[i], cur[i + 1]);
			// cout << cur[i] << cur[i + 1] << lca << endl;
			update(tin[lca], -2);
			update(tin[cur[i]], 1);
			update(tin[cur[i + 1]], 1);
		}
		
	}

	vi ans;

	FOR(i, 0, n - 1) {
		if (dep[edges[i].f] < dep[edges[i].s]) swap(edges[i].f, edges[i].s);

		if (query(tin[edges[i].f], tout[edges[i].f]) >= 2 * k) ans.pb(i + 1);
	}

	cout << ans.size() << endl;

	for (auto val: ans) cout << val << ' ';

		cout << endl;

}

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