Submission #896534

#	Time	Username	Problem	Language	Result	Execution time	Memory
896534		OAleksa	Railway (BOI17_railway)	C++14	100 / 100	197 ms	62468 KiB

railway

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 1e5 + 69;
const int lg = 17;
int up[N][lg];
int n, m, k, tin[N], tout[N], timer;
vector<int> g[N];
set<int> st[N], er[N];
set<tuple<int, int, int>> edges;
vector<int> ans;
bool anc(int v, int u) {
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}
int lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = lg - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
void dfs(int v, int p) {
	tin[v] = ++timer;
	up[v][0] = p;
	for (int i = 1;i < lg;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
	}
	tout[v] = timer;
}
void solve(int v, int p) {
	for (auto u : g[v]) {
		if (u == p)
			continue;
		solve(u, v);
		if (st[v].size() < st[u].size())
			swap(st[u], st[v]);
		for (auto x : st[u])
			st[v].insert(x);
	}
	for (auto u : er[v]) {
		assert(st[v].count(u) > 0);
		st[v].erase(u);
	}
	if (p != 0) {
		int a = v, b = p;
		if (a > b)
			swap(a, b);
		if (st[v].size() >= k) {
			auto u = *edges.lower_bound({a, b, -1});
			ans.push_back(get<2>(u));
		}
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
    cin >> n >> m >> k;
    for (int i = 1;i <= n - 1;i++) {
    	int a, b;
    	cin >> a >> b;
    	g[a].push_back(b);
    	g[b].push_back(a);
    	if (a > b)	
    		swap(a, b);
    	edges.insert({a, b, i});
    }
    dfs(1, 0);
    for (int i = 1;i <= m;i++) {
    	int s;
    	cin >> s;
    	vector<int> y(s);
    	for (int j = 0;j < s;j++)
    		cin >> y[j];
    	int lc = y[0];
    	for (int j = 1; j < s;j++)
    		lc = lca(lc, y[j]);
    	er[lc].insert(i);
    	for (int j = 0;j < s;j++) {
    		if (y[j] != lc)
    			st[y[j]].insert(i);
    	}
    }
    solve(1, 0);
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (auto u : ans)
    	cout << u << " ";
  }
  return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void solve(long long int, long long int)':
railway.cpp:58:20: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   58 |   if (st[v].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