Submission #1270895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270895		thuhienne	Railway (BOI17_railway)	C++20	100 / 100	81 ms	24768 KiB

railway

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

const int LOG = 16;

int n,m,k;

struct canh {
	int u,v;
	int other (const int & x) {
		return u ^ v ^ x;
	}
} edge[100009];

vector <int> adj[100009];

int tin[100009],timedfs;
int up[100009][LOG + 1],h[100009];

void dfs(int node,int par) {
	tin[node] = ++timedfs;
	for (auto x : adj[node]) {
		int child = edge[x].other(node);
		if (child == par) continue;
		
		h[child] = h[node] + 1;
		
		up[child][0] = node;
		for (int i = 1;i <= LOG;i++) {
			up[child][i] = up[up[child][i - 1]][i - 1];
		}
		dfs(child,node);
	}
}

int sum[100009];

int lca(int u,int v) {
	if (h[u] < h[v]) swap(u,v);
	int diff = h[u] - h[v];
	for (int i = LOG;i >= 0;i--) if (diff >> i & 1) u = up[u][i];
	if (u == v) return u;
	for (int i = LOG;i >= 0;i--) if (up[u][i] != up[v][i]) {
		u = up[u][i];
		v = up[v][i];
	}
	return up[u][0];
}

void increase(int u,int v) {
	sum[u]++;
	sum[v]++;
	sum[lca(u,v)] -= 2;
}

vector <int> print;

void redfs(int node,int par) {
	int d;
	for (auto x : adj[node]) {
		int child = edge[x].other(node);
		if (child == par) {
			d = x;
			continue;
		}
		
		redfs(child,node);
		sum[node] += sum[child];
	}
	if (sum[node] >= 2*k) print.push_back(d);
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	//freopen(".inp","r",stdin);
	//freopen(".out","w",stdout);
	cin >> n >> m >> k;
	for (int i = 1;i < n;i++) {
		cin >> edge[i].u >> edge[i].v;
		adj[edge[i].u].push_back(i);
		adj[edge[i].v].push_back(i);
	}
	dfs(1,-1);
	while (m--) {
		int num;cin >> num;
		vector <int> plan(num,0);
		
		for (int i = 0;i < num;i++) cin >> plan[i];
		sort(plan.begin(),plan.end(),[] (int a,int b) {
			return tin[a] < tin[b];
		});
		
		plan.push_back(plan[0]);
		for (int i = 1;i < plan.size();i++) {
			increase(plan[i - 1],plan[i]);
		}
	}
	redfs(1,-1);
	
	sort(print.begin(),print.end());
	cout << print.size() << '\n';
	for (auto a : print) cout << a << " ";
}

/*
  Nho doi vai em gay
			  co gai ay ngoi duoi goc pho nen tho ...
*/

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