Submission #1316585

#TimeUsernameProblemLanguageResultExecution timeMemory
1316585finalpoiRailway (BOI17_railway)C++20
100 / 100
58 ms24556 KiB
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
template <typename T> using vec=vector<T>;

constexpr char nl='\n';
#define fi first
#define se second
#define pb push_back
#define sz(c) (int)(c).size()
#define all(c) c.begin(),c.end()
#define rep(a, b) for(decltype(b) a=0; a<b; ++a)

#ifdef LOCAL
#define DEBUG 1
#else
#define DEBUG 0
#endif
#define ifbug if constexpr(DEBUG)
#define bug(...) ifbug{cerr<<"["#__VA_ARGS__"]: ";bug__(__VA_ARGS__);cerr<<'\n';}
template <typename...A> void bug__(A&&...a){((cerr<<a<<' '),...);}

struct DebugStream {
    template <typename T>
    constexpr DebugStream& operator<<(T&& value) const {
        ifbug std::cerr<<std::forward<T>(value);
        return const_cast<DebugStream&>(*this);
    }
};
inline constexpr DebugStream cbug{};

constexpr int N=1e5+6;
constexpr int L=20;

vec<pair<int, int>> adj[N]; // {index krawedzi, wierzcholek}
int pre[N]; int post[N];
int dep[N];
int jmp[N][L];
int dp[N];
int ans[N];
int tmr=0;

void dfs(int a, int p) {
    dep[a]=dep[p]+1;
    jmp[a][0]=p;
    pre[a]=++tmr;
    for(const auto &[i, b]:adj[a]) {
        if(b!=p) {
            dfs(b, a);
        }
    }
    post[a]=++tmr;
}

void lift(int &a, int h) {
    for(int l=L-1; l>=0; --l) {
        if((h>>l)&1) {
            a=jmp[a][l];
        }
    }
}

int lca(int a, int b) {
    if(dep[a]<dep[b]) { swap(a, b); }
    lift(a, dep[a]-dep[b]);
    if(a==b) { return a; }
    for(int l=L-1; l>=0; --l) {
        int a2=jmp[a][l]; int b2=jmp[b][l];
        if(a2!=b2) { a=a2; b=b2; }
    }
    return jmp[a][0];
}

void dfs_dp(int a, int p, int i) {
    for(const auto &[j, b]:adj[a]) {
        if(b!=p) {
            dfs_dp(b, a, j);
            dp[a]+=dp[b];
        }
    }
    // bug(a, p, i, dp[a]);
    ans[i]=dp[a];
}

bool is_anc(int a, int b) {
    return pre[a]<=pre[b] && post[b]<=post[a];
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    // preprocess
    dfs(1, 0);
    for(int l=1; l<L; ++l) {
        for(int i=1; i<=n; ++i) {
            jmp[i][l]=jmp[jmp[i][l-1]][l-1];
        }
    }

    // queries
    rep(_, m) {
        int s;
        cin>>s;
        vec<int> wie(s);
        for(int i=0; i<s; ++i) { cin>>wie[i]; }
        sort(all(wie), [&](int a, int b) {
            return pre[a]<pre[b];
        });
        
        for(int i=1; i<s; ++i) {
            int przodek=lca(wie[i], wie[i-1]);
            wie.pb(przodek);
        }

        sort(all(wie), [&](int a, int b) {
            return pre[a]<pre[b];
        });
        wie.erase(unique(all(wie)), wie.end());
        
        stack<int> st;
        st.push(wie[0]);
        for(int i=1; i<sz(wie); ++i) {
            int x=wie[i];
            while(!st.empty() && !is_anc(st.top(), x)) { st.pop(); }
            int parent=st.top();
            dp[x]+=1;
            dp[parent]-=1;
            st.push(x);
        }
    }

    dfs_dp(1, 0, 0);
    vec<int> kra;
    for(int i=1; i<=n-1; ++i) {
        if(ans[i]>=k) { kra.pb(i); }
    }

    cout<<sz(kra)<<nl;
    sort(all(kra));
    for(const auto &i:kra) { cout<<i<<' '; }
    cout<<nl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...