Submission #927922

#	Time	Username	Problem	Language	Result	Execution time	Memory
927922		TAhmed33	Railway (BOI17_railway)	C++98	100 / 100	364 ms	56340 KiB

railway

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
int n, m, k;
vector <int> adj[MAXN];
int t = 0;
int in[MAXN], out[MAXN], dep[MAXN], p[MAXN];
void dfs (int pos, int par = 0) {
	in[pos] = ++t;
	p[pos] = par;
	for (auto j : adj[pos]) {
		if (j == par) continue;
		dep[j] = 1 + dep[pos];
		dfs(j, pos);
	}
	out[pos] = t;
}
int dp[18][MAXN];
int jump (int a, int b) {
	for (int i = 17; i >= 0; i--) {
		if (b & (1 << i)) {
			a = dp[i][a];
		}
	}
	return a;
}
int lca (int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);
	b = jump(b, dep[b] - dep[a]);
	if (a == b) return a;
	for (int i = 17; i >= 0; i--) {
		int x = dp[i][a], y = dp[i][b];
		if (x && y && x != y) {
			a = x; b = y;
		}
	}
	return jump(a, 1);
}
map <int, int> vals[MAXN];
void insert (int a, int b, int c) {
	if (a == b) return;
	vals[a][c]++;
	vals[b][c]--;
}
vector <int> kk;
void dfs2 (int pos, int par) {
	for (auto j : adj[pos]) {
		if (j == par) continue;
		dfs2(j, pos);
		if (vals[j].size() > vals[pos].size()) vals[j].swap(vals[pos]);
		for (auto p : vals[j]) {
			vals[pos][p.first] += p.second;
			if (vals[pos][p.first] == 0) vals[pos].erase(p.first);
		}
		vals[j].clear();
	}
	if (vals[pos].size() >= k) {
		kk.push_back(pos);
	}
}
map <pair <int, int>, int> lll;
int main () {
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
		lll[{a, b}] = lll[{b, a}] = i;
	}
	dfs(1);
	for (int i = 1; i <= n; i++) dp[0][i] = p[i];
	for (int j = 1; j <= 17; j++) {
		for (int i = 1; i <= n; i++) {
			dp[j][i] = dp[j - 1][dp[j - 1][i]];
		}
	}
	while (m--) {
		int x;
		cin >> x;
		vector <int> dd(x);
		for (auto &i : dd) cin >> i;
		sort(dd.begin(), dd.end(), [&] (int a, int b) {
			return in[a] < in[b];
		});
		for (int i = 1; i < (int)dd.size(); i++) {
			int x = lca(dd[i], dd[i - 1]);
			insert(dd[i], x, m);
			insert(dd[i - 1], x, m);
		}
	}
	dfs2(1, -1);
	cout << (int)kk.size() << '\n';
	for (auto &i : kk) {
		i = lll[{i, p[i]}];
	}
	sort(kk.begin(), kk.end());
	for (auto i : kk) cout << i << " ";
}

Compilation message (stderr)

railway.cpp: In function 'void dfs2(int, int)':
railway.cpp:57:23: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |  if (vals[pos].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