Submission #1197269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197269		Sofiatpc	Railway (BOI17_railway)	C++20	36 / 100	131 ms	33724 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;
vector<int> adj[MAXN], id[MAXN];
int pai[MAXN], pid[MAXN], tin[MAXN], tout[MAXN], bit[MAXN], n , t;
map<int,int> mp[MAXN];

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 merge(int p , int f){
	if(sz(mp[p]) > sz(mp[f])){
		for(auto it : mp[f]){
			if(mp[p].find(it.fi) == mp[p].end()) mp[p][it.fi] = it.sc;
			else{
				update( tin[it.sc], 1);
				update( tin[mp[p][it.fi]], 1);
				update( tin[p] , -2);
				mp[p][it.fi] = p;
			}
		}
	}
	else{
		for(auto it : mp[p]){
			if(mp[f].find(it.fi) == mp[f].end()) mp[f][it.fi] = it.sc;
			else{
				update( tin[it.sc], 1);
				update( tin[mp[f][it.fi]], 1);
				update( tin[p] , -2);
				mp[f][it.fi] = p;
			}
		}
		swap(mp[f],mp[p]);
	}
	mp[f].clear();
}

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

		if(viz != pai[s]){
			dfs(viz);
			merge(s,viz);
		}
	}
}

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]){
			pai[viz] = s;
			pid[viz] = id[s][i];

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

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);
	}

	for(int i = 1; i <= m; i++){
		int s; cin>>s;
		for(int j = 1; j <= s; j++){
			int v; cin>>v;
			mp[v][i] = v;
		}
	}

	dfsIni(1);
	dfs(1);

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

	cout<<sz(ans)<<"\n";
	for(auto it : ans)cout<<it<<" ";
	cout<<"\n";
}

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