Submission #534145

#	Time	Username	Problem	Language	Result	Execution time	Memory
534145		xuliu	Railway (BOI17_railway)	C++17	100 / 100	108 ms	27640 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

const int mod = 1e9 + 7;
const ll infL = 1e18 + 7;
const int inf = 1e9 + 7;

const int N = 1e5 + 4, M = 20;
vector<int> V[N];
int tin[N], tout[N], depth[N], jump[N][M], pref[N];
int T = 1;

void dfs(int v, int p=0, int d=0) {
	depth[v] = d+1;
	tin[v] = T++;
	jump[v][0] = p;
	for(int u : V[v]) {
		if(u != p) dfs(u, v, d+1);
	}
	tout[v] = T++;
}

int jmp(int x, int k) {
	for(int i=0; i<M; i++) {
		if((1<<i) & k) x = jump[x][i];
	}
	return x;
}

int lca(int a, int b) {
	if(depth[a] < depth[b]) swap(a, b);
	a = jmp(a, depth[a]-depth[b]);
	if(a == b) return a;
	for(int i=M-1; i>=0; i--) {
		int xa = jump[a][i], xb = jump[b][i];
		if(xa != xb) { a = xa; b = xb; }
	}
	return jump[a][0];
}

int ans[N];
void dfs2(int v, int p=0) {
	ans[v] = pref[v];
	for(int u : V[v]) {
		if(u != p) {
			dfs2(u, v);
			ans[v] += ans[u];
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m, k; cin>>n>>m>>k;
	vector<pair<int, int>> E;
	for(int i=1; i<n; i++) {
		int a, b; cin>>a>>b;
		V[a].push_back(b);
		V[b].push_back(a);
		E.push_back({a, b});
	}
	dfs(1);
	for(int j=1; j<M; j++) {
		for(int i=1; i<=n; i++) jump[i][j] = jump[jump[i][j-1]][j-1];
	}
	for(int z=0; z<m; z++) {
		int s; cin>>s;
		vector<pair<int, int>> cc;
		for(int i=0; i<s; i++) {
			int a; cin>>a;
			cc.push_back({tin[a], a});
		}
		sort(cc.begin(), cc.end());
		for(int i=0; i<s; i++) {
			int a = cc[i].second, b = cc[(i+1)%s].second;
			// add on path (a, b) value 1
			int lc = lca(a, b);
			pref[a]++; pref[b]++; pref[lc]-=2;
		}
	}
	dfs2(1);
	vector<int> result;
	for(int i=0; i<(n-1); i++) {
		auto e = E[i];
		int a = e.first, b = e.second;
		if(depth[a] > depth[b]) swap(a, b);
		if(ans[b] >= 2*k) result.push_back(i+1);
		debug cerr<<"ans["<<b<<"] = "<<ans[b]<<"\n";
	}
	cout<<(int) result.size()<<"\n";
	for(int x : result) cout<<x<<" ";
}

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