Submission #1199419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199419		Sofiatpc	Railway (BOI17_railway)	C++20	100 / 100	67 ms	29192 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define fi first
#define sc second
const int MAXN = 1e5+5, MAX = 17;
vector<int> adj[MAXN], id[MAXN];
int pai[MAXN], pid[MAXN], dist[MAXN], tin[MAXN], tout[MAXN], bit[MAXN], sparse[MAX+5][MAXN], n , t;

void update(int i, int x){
	for(; i <= n; i += i&-i)
		bit[i] += x;
}

int query(int i){
	if(i <= 0)return 0;
	int ans = 0;
	for(; i > 0; i-= i&-i)
		ans += bit[i];
	return ans;
}

void dfsIni(int s){
	t++; tin[s] = t;
	for(int i = 0; i < sz(adj[s]); i++){
		int viz = adj[s][i];

		if(viz != pai[s]){
			sparse[0][viz] = s;
			pai[viz] = s;
			dist[viz] = dist[s]+1;
			pid[viz] = id[s][i];

			dfsIni(viz);
		}
	}
	tout[s] = t;
}

int lca(int a, int b){
	if(dist[a] < dist[b])swap(a,b);

	int d = dist[a]-dist[b];
	for(int i = 0; i < MAX; i++)
		if(d & (1<<i))a = sparse[i][a];
	if(a == b)return a;
	for(int i = MAX; i >= 0; i--)
		if(sparse[i][a] != sparse[i][b]){
			a = sparse[i][a];
			b = sparse[i][b];
		}

	return sparse[0][a];
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int m,k; cin>>n>>m>>k;
	for(int i = 1; i < n; i++){
		int a,b; cin>>a>>b;
		adj[a].push_back(b); id[a].push_back(i);
		adj[b].push_back(a); id[b].push_back(i);
	}

	dfsIni(1);

	for(int i = 1; i <= MAX; i++)
		for(int j = 1; j <= n; j++)
			if(sparse[i-1][j] != 0)sparse[i][j] = sparse[i-1][sparse[i-1][j]];

	for(int i = 1; i <= m; i++){
		int s; cin>>s;

		vector< pair<int,int> > o;
		for(int j = 1; j <= s; j++){
			int v; cin>>v;
			o.emplace_back(tin[v], v);
		}
		sort(o.begin(),o.end());

		for(int j = 0; j < s-1; j++){
			update( o[j].fi, 1);
			update( o[j+1].fi, 1);
			update( tin[ lca(o[j].sc, o[j+1].sc)] , -2);
		}
		update( o[s-1].fi, 1);
		update( o[0].fi, 1);
		update( tin[ lca(o[s-1].sc, o[0].sc)] , -2);
	}

	vector<int> ans;
	for(int i = 2; i <= n; i++)
		if(query(tout[i])-query(tin[i]-1) >= 2*k)ans.push_back(pid[i]);

	sort(ans.begin(),ans.end());

	cout<<sz(ans)<<"\n";
	for(auto it : ans)cout<<it<<" ";
	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