Submission #1170290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170290		nguyenkhangninh99	Railway (BOI17_railway)	C++17	100 / 100	91 ms	32708 KiB

railway

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

const int maxn = 1e5 + 5;

vector<int> g[maxn];
int h[maxn], up[maxn][22], tin[maxn], out[maxn], cost[maxn], timeDfs = 0;
map<pair<int, int>, int> mp;

void dfs(int u){
    tin[u] = ++timeDfs;
	for(int v: g[u]){
		if(v == up[u][0]) continue;
		
		h[v] = h[u] + 1;
		up[v][0] = u; 

		for(int j = 1; j <= 21; j++) up[v][j] = up[up[v][j - 1]][j - 1];
		
		dfs(v);
	}
    out[u] = timeDfs;
}
 
int lca(int u, int v){
	if(h[u] != h[v]){
		if(h[u] < h[v]) swap(u, v);
		
		int k = h[u] - h[v];
		
		for(int j = 0; (1 << j) <= k; j++){
			if((k >> j) & 1){
				u = up[u][j];
			}
		}
	}
	
	if(u == v)  return u;
	
	int k = __lg(h[u]);
	
	for(int j = k; j >= 0; j--) {
		if(up[u][j] != up[v][j]){
			u = up[u][j];
			v = up[v][j];
		}
	}
	
	return up[u][0];
}


vector<int> vert, ans;

//dựng cây ảo
void build(){
    //sắp xếp lại theo tin để thêm lca và dựng cây
    sort(vert.begin(), vert.end(), [&](int c, int d) {return tin[c] < tin[d];});

    int k = vert.size();
    for(int i = 0; i < k - 1; i++) vert.push_back(lca(vert[i], vert[i + 1]));

    //sắp xếp lại theo tin và nén
    sort(vert.begin(), vert.end(), [&](int c, int d) {return tin[c] < tin[d];});
    vert.erase(unique(vert.begin(), vert.end()), vert.end());

    stack<int> st;
    for(int u: vert) {
        while(st.size() && !(tin[st.top()] <= tin[u] && tin[u] <= out[st.top()])) st.pop();
        if(st.size()){
            cost[st.top()]--;
            cost[u]++;
        }
        st.push(u);
    }
}
int kk;

void dfs2(int u, int pre){
    for(int v: g[u]){
        if(v == pre) continue;
        dfs2(v, u);
        cost[u] += cost[v];
    }
    if(cost[u] >= kk && u > 1) ans.push_back(mp[{min(u, up[u][0]), max(u, up[u][0])}]);
}
void solve(){
    int n, m, k; cin >> n >> m >> k;
    kk = k;

    for(int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        mp[{min(u, v), max(u, v)}] = i;

    }

    dfs(1);

    while(m--){
        int sz; cin >> sz;
        vert.resize(sz);

        for(int i = 0; i < sz; i++) cin >> vert[i];

        build();
    }

    dfs2(1, 0);

    cout << ans.size() << "\n";
    sort(ans.begin(), ans.end());
    for(int x: ans) cout << x << " ";
}


 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    solve();
}

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