Submission #1306181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306181		Robert_junior	Railway (BOI17_railway)	C++20	36 / 100	66 ms	35704 KiB

railway

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define all(x) x.begin(), x.end()
#define ins insert
#define pb push_back
#define F first
#define S second
#define bt bitset<5010>
const int N = 1e5 + 100, K = 1610;
const int mod = 998244353;
vector<pair<int, int>>g[N];
vector<int>g1[N];
int f[N], tin[N], tout[N], timer, up[N][20];
int n, m, k;
void dfs(int v, int p){
	tin[v] = timer++;
	up[v][0] = p;
	for(int i = 1; i < 20; i++){
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	for(auto [to, idx] : g[v]){
		if(to == p) continue;
		dfs(to, v);
	}
	tout[v] = timer;
}
int F(int u, int v){
	return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int lca(int u, int v){
	if(F(u, v)) return u;
	if(F(v, u)) return v;
	for(int i = 19; i >= 0; i--){
		if(!F(up[u][i], v)) u = up[u][i];
	}
	return up[u][0];
}
void add(int idx, int vl){
	for(; idx < N; idx |= (idx + 1)){
		f[idx] += vl;
	}
}
int get(int r){
	int res = 0;
	for(; r >= 0; r = (r & (r + 1)) - 1){
		res += f[r];
	}
	return res;
}
int get(int l, int r){
	return get(r - 1) - get(l - 1);
}
void Path(int v, int l, int vl){
	add(tin[l], -vl);
	add(tin[v], vl);
}
void V(int v, int vl){
	add(tin[v], vl);
	if(up[v][0] != v) add(tin[up[v][0]], -vl);
}
int getV(int v){
	return get(tin[v], tout[v]);
}
bool cmp(int x, int y){
	return tin[x] < tin[y];
}
void dfs1(int v, int p){
	for(auto to : g1[v]){
		Path(to, v, 1);
		dfs1(to, v);
	}
}
void build(vector<int>v){
	int z = v.size();
	sort(all(v), cmp);
	for(int i = 0; i < z - 1; i++){
		v.pb(lca(v[i], v[i + 1]));
	}
	sort(all(v), cmp);
	v.erase(unique(all(v)), v.end());
	vector<int>v1;
	z = v.size();
	for(int i = 0; i < z; i++){
		int u = v[i];
		while(v1.size() >= 2 && !F(v1.back(), u)){
			g1[v1[v1.size() - 2]].pb(v1.back());
			v1.pop_back();
		}
		v1.pb(u);
	}
	while(v1.size() >= 2){
		g1[v1[v1.size() - 2]].pb(v1.back());
		v1.pop_back();
	}
	dfs1(v1[0], v1[0]);
	for(auto it : v){
		g1[it].clear();
	}
}
void solve(){
	cin>>n>>m>>k;
	for(int i = 1; i <= n - 1; i++){
		int u, v;
		cin>>u>>v;
		g[u].pb({v, i});
		g[v].pb({u, i});
	}
	dfs(1, 1);
	for(int i = 1; i <= m; i++){
		vector<int>v;
		int z;
		cin>>z;
		for(int j = 1; j <= z; j++){
			int x;
			cin>>x;
			v.pb(x);
		}
		build(v);
	}
	vector<int>ans;
	for(int i = 2; i <= n; i++){
		if(getV(i) >= k){
		    for(auto [to, idx] : g[i]){
		        if(to == up[i][0]) ans.pb(idx);
		    }
		}
	}
	cout<<ans.size()<<'\n';
	for(auto it : ans) cout<<it<<' ';
}
main(){
	ios_base :: sync_with_stdio(false); 
	cin.tie(nullptr);
	int t = 1;
	//cin>>t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

railway.cpp:133:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  133 | main(){
      | ^~~~

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