Submission #758790

#	Time	Username	Problem	Language	Result	Execution time	Memory
758790		Hacv16	Railway (BOI17_railway)	C++17	100 / 100	127 ms	47620 KiB

railway

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

const int LOG = 22;
const int MAX = 5e5 + 10;
const int INF = 0x3f3f3f3f;
 
int n, m, k, f[MAX], dp[MAX][LOG], h[MAX], tin[MAX], a[MAX], timer;
vector<pair<int, int>> adj[MAX];
vector<int> ids;

void dfs(int u, int p){
	tin[u] = ++timer;
	dp[u][0] = p; h[u] = h[p] + 1;

   	for(int i = 1; i < LOG; i++)
        dp[u][i] = dp[ dp[u][i - 1] ][i - 1];

	for(auto [v, id] : adj[u]){
		if(v == p) continue;
		dfs(v, u);
	}
}

int lca(int u, int v){
	if(h[u] < h[v]) swap(u, v);
	int jump = h[u] - h[v];
 
	for(int j = LOG - 1; j >= 0; j--)
		if(jump & (1 << j)) u = dp[u][j];
 
	if(u == v) return v;
 
	for(int j = LOG - 1; j >= 0; j--)
		if(dp[u][j] != dp[v][j]) u = dp[u][j], v = dp[v][j];
 
	return dp[u][0];
}

void calcResp(int u, int p, int id){
    for(auto [v, nx] : adj[u]){
        if(v == p) continue;
        calcResp(v, u, nx);
        f[u] += f[v];
    }

    if(f[u] >= k * 2 && id != 0)
    	ids.push_back(id);
}

int32_t main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m >> k;

	for(int i = 1; i < n; i++){
		int u, v; cin >> u >> v;

		adj[u].emplace_back(v, i);
		adj[v].emplace_back(u, i);
	}
	
	dfs(1, 0);
    
	for(int i = 1; i <= m; i++){
        int n; cin >> n;
        for(int i = 1; i <= n; i++)
           cin >> a[i];

        sort(a + 1, a + n + 1, [&](int i, int j){
        	return tin[i] < tin[j];
        });

        a[n + 1] = a[1];

        for (int i = 1; i <= n; i++) {
            f[a[i]]++; f[a[i + 1]]++;
            f[lca(a[i], a[i + 1])] -= 2;
        }
    }

	calcResp(1, 0, 0);

	cout << ids.size() << '\n';

	sort(ids.begin(), ids.end());
	for(auto x : ids) cout << x << ' ';
}

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