Submission #1199429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199429		ChuanChen	Railway (BOI17_railway)	C++20	100 / 100	64 ms	22408 KiB

railway

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

const int MAXN = 1e5+5, MAXK = 18;
typedef pair<int, int> pii;

int n, m, threshold;

/////////////////
vector<pii> adj[MAXN];
int pre[MAXN], pos[MAXN], dp[MAXN][MAXK], prof[MAXN], tempo, p_edge[MAXN];
void dfs(int no, int anc){
	pre[no] = ++tempo;
	prof[no] = prof[anc]+1;
	dp[no][0] = anc;
	for(int k = 1; k < MAXK; k++)
		dp[no][k] = dp[dp[no][k-1]][k-1];
	for(auto &[v, id] : adj[no]) if(pre[v] == 0){
		p_edge[v] = id;
		dfs(v, no);
	}
	pos[no] = tempo;
}

int lca(int a, int b){
	if(prof[a] < prof[b]) swap(a, b);
	int d = prof[a]-prof[b];
	for(int k = 0; k < MAXK; k++) if((1<<k)&d)a = dp[a][k];
	if(b == a) return b;

	for(int k = MAXK-1; k >= 0; k--){
		if(dp[a][k] != dp[b][k]){
			a = dp[a][k];
			b = dp[b][k];
		}
	}
	return dp[a][0];
}
/////////////////
bool cmp(int a, int b){
	return pre[a] < pre[b];
}
/////////////////
int bit[MAXN];
void update(int i, int val){
	for(; i <= n; i += (-i)&i) bit[i] += val;
}
int query(int l, int r){
	int ans = 0;
	for(;r > 0; r -= (-r)&r) ans += bit[r];
	for(l--; l > 0; l -= (-l)&l) ans -= bit[l];
	return ans;
}
/////////////////
int main(){
    cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> threshold;

	for(int i = 1; i < n; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back({b, i});
		adj[b].push_back({a, i});
	} 
	dfs(1, 1);
	while(m--){
		int s; cin >> s;
		vector<int> nb(s);
		for(int &v : nb) cin >> v;
		sort(nb.begin(), nb.end(), cmp);
		for(int i = 0; i < s; i++){
			int a = nb[i], b = nb[(i+1)%s];
			update(pre[a], 1);
			update(pre[b], 1);
			update(pre[lca(a, b)], -2);
		}
	}
	vector<int> ans;
	for(int i = 2; i <= n; i++)
		if(query(pre[i], pos[i]) >= 2*threshold)
			ans.push_back(p_edge[i]);
	sort(ans.begin(), ans.end());
	cout << ans.size() << '\n';
	for(int a : ans) cout << a << ' ';
	cout << "\n";
}

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