Submission #927165

#	Time	Username	Problem	Language	Result	Execution time	Memory
927165		a_l_i_r_e_z_a	Railway (BOI17_railway)	C++17	100 / 100	61 ms	23640 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;
const int inf = 1e9 + 7;
int n, m, k, ans, cnt[maxn], a[maxn], sz[maxn];
vector<pii> adj[maxn];
vector<int> col[maxn], vec;
bool mark[maxn];

int get_sz(int v, int p){
    for(auto [u, i]: adj[v]){
        if(u != p) sz[v] += get_sz(u, v);
    }
    return ++sz[v];
}

void reset(){
    for(auto v: vec){
        for(auto c: col[v]){
            a[c]--;
            if(a[c] == cnt[c] - 1) ans++;
            else if(a[c] == 0) ans--;
        }
    }
    vec.clear();
}

void add(int v){
    vec.pb(v);
    for(auto c: col[v]){
        a[c]++;
        if(a[c] == 1) ans++;
        else if(a[c] == cnt[c]) ans--;
    }
}

void dfs2(int v, int p){
    add(v);
    for(auto [u, i]: adj[v]) if(u != p) dfs2(u, v);
}

void dfs(int v, int p, int e){
    int bc = -1, bi = -1;
    for(auto [u, i]: adj[v]){
        if(u != p) if(bc == -1 || sz[u] > sz[bc]){
            bc = u;
            bi = i;
        }
    }
    for(auto [u, i]: adj[v]){
        if(u != p && u != bc){
            dfs(u, v, i);
            reset();
        }
    }
    if(bc != -1) dfs(bc, v, bi);
    for(auto [u, i]: adj[v]){
        if(u != p && u != bc){
            dfs2(u, v);
        }
    }
    add(v);
    if(ans >= k) mark[e] = 1;
}

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));
    }
    for(int i = 0; i < m; i++){
        cin >> cnt[i];
        for(int j = 0; j < cnt[i]; j++){
            int u; cin >> u;
            col[u].pb(i);
        }
    }
    get_sz(1, -1);
    dfs(1, -1, -1);
    vector<int> res;
    for(int i = 0; i < n - 1; i++) if(mark[i]) res.pb(i);
    cout << res.size() << '\n';
    for(auto u: res) 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