Submission #1115817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115817		vjudge1	Railway (BOI17_railway)	C++17	100 / 100	82 ms	49612 KiB

railway

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;

vector<pair<int, int>> adj[N + 8];
int pe_id[N + 8];
int h[N + 8], tin[N + 8], tout[N + 8];
pair<int, int> euler[N * 2 + 8];
int upd[N + 8];

void add_edge(int u, int v, int id) {adj[u].push_back({v, id}); adj[v].push_back({u, id});}

int timer = 0;
void DFS_EulerTour(int u, int p) {
	int v, id;
	tin[u] = ++timer; euler[timer] = {h[u], u};
	for (pair<int, int> E : adj[u]) if (E.first != p) {
		tie(v, id) = E; h[v] = h[u] + 1; pe_id[v] = id; 
		DFS_EulerTour(v, u); euler[++timer] = {h[u], u};
	}
	tout[u] = timer;
}

pair<int, int> SpT[N * 2 + 8][20];

int lg;
void build() {
	for (lg = 0; lg <= __lg(timer); ++lg) for (int i = 1; i + (1 << lg) - 1 <= timer; ++i) 
		if (!lg) SpT[i][lg] = euler[i];
		else SpT[i][lg] = min(SpT[i][lg - 1], SpT[i + (1 << (lg - 1))][lg - 1]);
}

pair<int, int> range_min(int l, int r) {
	lg = __lg(r - l + 1);
	return min(SpT[l][lg], SpT[r + 1 - (1 << lg)][lg]);
}

int LCA(int u, int v) {
	if (tin[u] > tin[v]) swap(u, v);
	return range_min(tin[u], tin[v]).second;
}

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

void DFS(int u, int p) {
	for (pair<int, int> E : adj[u]) if (E.first != p) {
		DFS(E.first, u);
		upd[u] += upd[E.first];
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, q, k, u, v; cin >> n >> q >> k;
	for (int i = 1; i < n; ++i) cin >> u >> v, add_edge(u, v, i);
	DFS_EulerTour(1, 0); build();
	int sz; vector<int> nodes;
	while (q--) {
		cin >> sz; nodes.clear();
		while (sz--) cin >> u, nodes.push_back(u);
		sort(nodes.begin(), nodes.end(), custom); nodes.push_back(nodes[0]);
		for (int i = 0; i + 1 < nodes.size(); ++i) {
			++upd[nodes[i]]; ++upd[nodes[i + 1]];
			upd[LCA(nodes[i], nodes[i + 1])] -= 2;
		}
		// for (int i : nodes) cout << i << ' ';
		// cout << '\n';
	}
	DFS(1, 0); vector<int> ans; 
	for (int i = 2; i <= n; ++i) if (upd[i] >= k + k) ans.push_back(pe_id[i]);
	sort(ans.begin(), ans.end()); cout << ans.size() << '\n';
	for (int i : ans) cout << i << ' ';
}

Compilation message (stderr)

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

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