Submission #1167785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167785		altern23	Railway (BOI17_railway)	C++20	100 / 100	105 ms	48904 KiB

railway

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll N = 1e5;
const ll INF = 4e18;
const ll MOD = 998244353;

vector<pii> adj[N + 5];
ll tin[N + 5], tout[N + 5], p[N + 5], dist[N + 5];
ll dp[N + 5], edges[N + 5];

ll t = 0;
void dfs(ll idx, ll par){
    if(idx != 1) p[idx] = par;
    tin[idx] = ++t;
    for(auto [i, j] : adj[idx]){
        if(i != par){
            dist[i] = dist[idx] + 1;
            dfs(i, idx);
        }
    }
    tout[idx] = t;
}

void dfs2(ll idx, ll par){
    for(auto [i, j] : adj[idx]){
        if(i != par){
            dfs2(i, idx);
            dp[idx] += dp[i];
            edges[j] = dp[i];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n, m, k; cin >> n >> m >> k;
        for(int i = 1; i <= n - 1; i++){
            ll u, v; cin >> u >> v;
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }

        dfs(1, -1);

        vector<vector<ll>> up(n + 5, vector<ll>(30));
        for(int LOG = 0; LOG < 30; LOG++){
            for(int i = 1; i <= n; i++){
                if(LOG == 0) up[i][LOG] = p[i];
                else up[i][LOG] = up[up[i][LOG - 1]][LOG - 1];
            }
        }
        
        auto binlift = [&](ll idx, ll len){
            for(int i = 0; i < 30; i++){
                if(len & (1LL << i)){
                    idx = up[idx][i];
                }
            }
            return idx;
        };

        auto get_lca = [&](ll a, ll b){
            if(dist[a] < dist[b]) swap(a, b);
            a = binlift(a, dist[a] - dist[b]);
            if(a == b) return a;
            for(int i = 29; i >= 0; --i){
                if(up[a][i] != up[b][i]){
                    a = up[a][i], b = up[b][i];
                }
            }
            return up[a][0];
        };
        
        for(int i = 1; i <= m; i++){
            ll s; cin >> s;
            vector<ll> v;
            for(int j = 1; j <= s; j++){
                ll x; cin >> x;
                v.push_back(x);
            }
            sort(v.begin(), v.end(), [&](ll a, ll b){
                return tin[a] < tin[b];
            });
            v.push_back(v[0]);

            // simulate dfs, satu edge divisit pas 2x
            for(int i = 1; i < v.size(); i++){
                ll LCA = get_lca(v[i - 1], v[i]);
                dp[v[i - 1]]++, dp[v[i]]++;
                dp[LCA] -= 2;
            }
        }

        dfs2(1, -1);

        vector<ll> ans;
        for(int i = 1; i <= n - 1; i++){
            if(edges[i] / 2 >= k){
                ans.push_back(i);
            }
        }
        cout << ans.size() << "\n";
        for(auto i : ans) cout << i << " ";
        cout << "\n";
    }   
}

/*

*/ 

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