Submission #395447

#	Time	Username	Problem	Language	Result	Execution time	Memory
395447		Nordway	Railway (BOI17_railway)	C++17	7 / 100	150 ms	25300 KiB

railway

#include <bits/stdc++.h>


using namespace std;

const int N = 1e5 + 1;

vector <pair<int, int>> g[N];
int timer, tin[N], tout[N], up[N][18];

void dfs(int v, int p = 1) {
	tin[v] = ++timer;
	up[v][0] = p;
	for (int i = 1; i <= 17; i++) up[v][i] = up[up[v][i - 1]][i - 1];
	for (pair<int, int> to : g[v]) {
		if (to.first != p) {
			dfs(to.first, v);
		}
	}
	tout[v] = timer;
}

bool upper(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
	if (upper(u, v)) return u;
	if (upper(v, u)) return v;
	for (int i = 17; i >= 0; i--) {
		if (!upper(up[u][i], v)) {
			u = up[u][i];
		}
	}
	return up[u][0];
}

bool cmp(int u, int v) {
	return tin[u] < tin[v];
}

int cnt[N], dp[N];

void dfs2(int v, int p = 1, int edg = 0) {
	for (pair<int, int> to : g[v]) {
		if (to.first != p) {
			dfs2(to.first, v, to.second);
			dp[v] += dp[to.first];
		}
	}
	cnt[edg] = dp[v];
}

int main(){

	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(make_pair(v, i));
		g[v].push_back(make_pair(u, i));
	}
	dfs(1);
	for (int i = 1; i <= m; i++) {
		int s;
		cin >> s;
		vector <int> S(s);
		for (int &a : S) {
			cin >> a;
		}
		sort(S.begin(), S.end(), cmp);
		for (int i = 0; i < S.size() - 1; i++) {
			int u = S[i], v = S[i + 1];
			int L = lca(u, v);
			dp[v]++;
			dp[L]--;
		}
	}
	dfs2(1);
	vector <int> ans;
	for (int i = 1; i < n; i++) {
		if (cnt[i] >= k) {
			ans.push_back(i);
		}
	}
	cout << ans.size() << "\n";
	for (int edg : ans) cout << edg << " ";
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int i = 0; i < S.size() - 1; i++) {
      |                   ~~^~~~~~~~~~~~~~

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