제출 #557509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
557509		fatemetmhr	Railway (BOI17_railway)	C++17	100 / 100	116 ms	28168 KiB

railway

// `Be name khoda` //

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb     push_back
#define all(x) x.begin(), x.end()
#define fi     first
#define se     second


const int maxn5 = 2e5 + 10;

int k, num = 0, cnt[maxn5], lim[maxn5];
int st[maxn5], ft[maxn5], ver[maxn5], ti = -1;
int sz[maxn5], big[maxn5], pared[maxn5];
vector <int> ans, req[maxn5];
vector <pair<int, int>> adj[maxn5];

inline void upd(int a, int val){
    //cout << "updating " << a << ' ' << val << endl;
    if(cnt[a] > 0 && cnt[a] < lim[a])
        num--;
    cnt[a] += val;
    if(cnt[a] > 0 && cnt[a] < lim[a])
        num++;
    //cout << "final value of " << num << ' ' << cnt[a] << ' ' << lim[a] << endl;
}

inline void dfs_det(int v){
    sz[v] = 1;
    big[v] = -1;
    st[v] = ++ti;
    ver[ti] = v;
    for(auto [u, id] : adj[v]) if(id != pared[v]){
        pared[u] = id;
        dfs_det(u);
        sz[v] += sz[u];
        if(big[v] == -1 || sz[big[v]] <= sz[u])
            big[v] = u;
    }
    ft[v] = ti;
    return;
}

inline void dfs_gooni(int v, bool keep){
    for(auto [u, id] : adj[v]) if(u != big[v] && id != pared[v])
        dfs_gooni(u, false);
    if(big[v] == -1){
        //cout << "here barg " << v << endl;
        for(auto u : req[v])
            upd(u, 1);
        if(num >= k)
            ans.pb(pared[v]);
        //cout << "having " << num << endl;
        if(keep)
            return;
        for(auto u : req[v])
            upd(u, -1);
        return;
    }
    dfs_gooni(big[v], true);
    for(auto u : req[v])
        upd(u, 1);
    for(auto [u, id] : adj[v]) if(u != big[v] && id != pared[v]) for(int i = st[u]; i <= ft[u]; i++)
        for(auto z : req[ver[i]])
            upd(z, 1);
    //cout << "ok " << v << ' ' << big[v] << ' '<< num << endl;
    if(num >= k)
        ans.pb(pared[v]);
    if(keep)
        return;
    for(int i = st[v]; i <= ft[v]; i++) for(auto u : req[ver[i]])
        upd(u, -1);
    return;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, m; cin >> n >> m >> k;
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        a--; b--;
        adj[a].pb({b, i});
        adj[b].pb({a, i});
    }
    for(int i = 0; i < m; i++){
        int l; cin >> l;
        lim[i] = l;
        while(l--){
            int a; cin >> a; a--;
            req[a].pb(i);
        }
    }

    pared[0] = n + 1;
    dfs_det(0);
    dfs_gooni(0, true);

    cout << ans.size() << endl;
    sort(all(ans));
    for(auto u : ans)
        cout << u + 1 << ' ';
    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