Submission #1306245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306245		Robert_junior	Railway (BOI17_railway)	C++20	100 / 100	87 ms	40520 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 tin[N], tout[N], timer, up[N][20], bc[N], head[N], sz[N], pf[N], cnt[N];
int n, m, k;
void init(int v, int p){
    sz[v] = 1;
    for(auto [to, idx] : g[v]){
        if(to == p) continue;
        init(to, v);
        sz[v] += sz[to];
        if(sz[to] > sz[bc[v]]) bc[v] = to;
    }
}
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];
	}
	if(bc[v]){
	    head[bc[v]] = head[v];
	    dfs(bc[v], v);
	}
	for(auto [to, idx] : g[v]){
		if(to == p || to == bc[v]) continue;
		head[to] = to;
		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 upp(int &a, int &b){
    while(!F(head[a], b)){
        pf[tin[head[a]]] += 1;
        pf[tin[a] + 1]--;
        a = up[head[a]][0];
    }
}
void upd(int u, int v){
    upp(u, v);
    upp(v, u);
    if(!F(u, v)) swap(u, v);
    pf[tin[u]]++;
    pf[tin[v] + 1]--;
}
bool cmp(int x, int y){
	return tin[x] < tin[y];
}
void dfs1(int v, int p){
	for(auto to : g1[v]){
	    cnt[v]++;
		upd(v, to);
		dfs1(to, v);
	}
	g1[v].clear();
}
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(auto it : v){
	    g1[it].clear();
	}
	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]);
}
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});
	}
	init(1, 1);
	head[1] = 1;
	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);
	}
	for(int i = 1; i <= n; i++){
	    pf[i] += pf[i - 1];
	}
	vector<int>ans;
	for(int i = 2; i <= n; i++){
		if(pf[tin[i]] - cnt[i] >= k){
		    for(auto [to, idx] : g[i]){
		        if(to == up[i][0]) ans.pb(idx);
		    }
		}
	}
	cout<<ans.size()<<'\n';
	sort(all(ans));
	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:143:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  143 | main(){
      | ^~~~

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