Submission #1310139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310139		muhammad-ahmad	Railway (BOI17_railway)	C++20	100 / 100	201 ms	50988 KiB

railway

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

#define int long long

const int N = 1e5 + 5;
const int L = 20;
vector<int> adj[N];
int cur, dist[N], par[N], sp[N][L], val[N], intime[N];

void sp_table(int u){
	sp[u][0] = par[u];
	int power = 1;
	for (int i = 1; i < L; i++){
		power *= 2;
		if (dist[u] < power) sp[u][i] = 0;
		else sp[u][i] = sp[sp[u][i - 1]][i - 1];
	}
}
 
void dfs(int u){
    intime[u] = ++cur;
	sp_table(u);
	for (auto i : adj[u]){
		if (par[u] != i){
			dist[i] = dist[u] + 1;
			par[i] = u;
			dfs(i);
		}
	}
}

int kth_ancestor(int u, int k){
	if (k == 0) return u;
	int power = 1;
	int ans = u;
	for (int i = 0; i < L; i++){
		if (k & power){
			ans = sp[ans][i]; 
		}
		power *= 2;
	}
	return ans;
}

int LCA(int u, int v){
	if (dist[u] > dist[v]) swap(u, v);
	v = kth_ancestor(v, dist[v] - dist[u]);
	if (u == v) return u;
	for (int i = L - 1; i >= 0; i--){
		if (sp[u][i] != sp[v][i]){
			u = sp[u][i];
			v = sp[v][i];
		}
	}
	return par[v];
}

int ans, k;
map<pair<int, int>, int> E;
vector<int> op;

void dfs1(int u = 1){
    for (auto v : adj[u]){
        if (v == par[u]) continue;
        dfs1(v);
        val[u] += val[v];
    }
    if (val[u] >= k) {ans++;
        op.push_back(E[{par[u], u}]);
    }
}

signed main(){
    int n, m; cin >> n >> m >> k;
    for (int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        E[{u, v}] = i;
        E[{v, u}] = i;
    }
    
    dfs(1);
    
    for (int i = 1; i <= m; i++){
        int s; cin >> s;
        vector<pair<int, int>> p;
        for (int j = 1; j <= s; j++){
            int x; cin >> x;
            val[x]++;
            p.push_back({intime[x], x});
        }
        sort(p.begin(), p.end());
        for (int j = 1; j < s; j++){
            int x = LCA(p[j].second, p[j - 1].second);
            val[x]--;
        }
        val[LCA(p[0].second,p.back().second)]--;
    }
    
    dfs1();
    cout << ans << endl;
    sort(begin(op), end(op));
    for (auto i : op) cout << i << ' ';
    cout << endl;
}

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