Submission #927809

#	Time	Username	Problem	Language	Result	Execution time	Memory
927809		a_l_i_r_e_z_a	Railway (BOI17_railway)	C++17	100 / 100	80 ms	24164 KiB

railway

// In the name of God
// Hope is last to die

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
// #define int long long    
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 1e5 + 5, lg = 20;
const int inf = 1e9 + 7;
int n, m, k, timer, par[maxn][lg], in[maxn], h[maxn], cnt[maxn], id[maxn];
vector<pii> adj[maxn];

void dfs(int v = 1, int p = 0){
    in[v] = timer++;
    par[v][0] = p;
    for(int i = 1; i < lg; i++) par[v][i] = par[par[v][i - 1]][i - 1];
    for(auto [u, i]: adj[v]){
        if(u == p) continue;
        id[i] = u;
        h[u] = h[v] + 1;
        dfs(u, v);
    }
}

int up(int v, int d){
    for(int i = 0; i < lg; i++){
        if(d & (1ll << i)) v = par[v][i];
    }
    return v;
}

int lca(int u, int v){
    if(h[u] > h[v]) swap(u, v);
    v = up(v, h[v] - h[u]);
    for(int i = lg - 1; i >= 0; i--){
        if(par[u][i] != par[v][i]){
            u = par[u][i];
            v = par[v][i];
        }
    }
    if(u == v) return u;
    return par[v][0];
}

bool cmp(int u, int v){
    return in[u] < in[v];
}

void solve(int v, int p){
    for(auto [u, i]: adj[v]){
        if(p == u) continue;
        solve(u, v);
        cnt[v] += cnt[u];
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> k;
    for(int i = 0; i < n - 1; i++){
        int u, v; cin >> u >> v;
        adj[u].pb(mp(v, i));
        adj[v].pb(mp(u, i));
    }
    dfs();
    while(m--){
        vector<int> vec;
        int s; cin >> s;
        for(int i = 0; i < s; i++){
            int u; cin >> u;
            vec.pb(u);
        }
        sort(all(vec), cmp);
        for(int i = 0; i < s; i++){
            int l = lca(vec[i], vec[(i + 1) % s]);
            cnt[l]--;
            cnt[vec[i]]++;
        }
    }
    solve(1, 0);
    vector<int> ans;
    for(int i = 0; i < n - 1; i++) if(cnt[id[i]] >= k) ans.pb(i);
    cout << ans.size() << '\n';
    for(auto u: ans) cout << u + 1 << ' ';
    cout << '\n';

    return 0;
}

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