Submission #410820

#TimeUsernameProblemLanguageResultExecution timeMemory
410820MalheirosRailway (BOI17_railway)C++17
36 / 100
123 ms23680 KiB
#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
 
const int maxn=1e5+10;
const int maxlog=20;
 
struct fenwick{
 
    ll* arr;
    int size;
    fenwick(int n){
        arr= new ll[n+1];
        for (int i=0;i<=n;i++) arr[i]=0;
        size=n;
    }
    fenwick(vector<int>& v){
        int n=v.size();
        arr = new ll[n+1];
        size=n;
        for (int i=0;i<n;i++){
            arr[i+1]=v[i];
        }
        build();
    }
    void build () {
        for (int i=1;i<=size;i++){
            int j= i + (i & (-i));
            if (j<=size)arr[j]+=arr[i];
        }
    }
    void update(int i,int delta){
 
        for (;i<=size;i += i&(-i)){
            arr[i]+=delta;
        }
    }
    ll query(int i){
        ll soma=0;
        for (;i;i-= i &(-i))soma+=arr[i];
        return soma;
    }
    ll query(int l,int r){
        if (l==1)return query(r);
        return query(r)-query(l-1);
    }
};
 
vector<pair<int,int>> grafo[maxn];
 
int ddepth[maxn];
int pai[maxn];
int beg[maxn]; int en[maxn]; int ver[maxn];
int tempo=0;
int dp[maxn][maxlog];
int volta[maxn];
void dfs(int u,int p,int cc=0){
    pai[u]=p;
    tempo++;
    beg[u]=tempo;
    ddepth[u]=cc;
    for (auto k:grafo[u]) if (k.first!=p){
        volta[k.first]=k.second;
        dfs(k.first,u,cc+1); 
    } 
    en[u]=tempo;
}
 
int jmp(int a,int j){
    for (int i=0;i<maxlog;i++)if ((j>>i) & 1) a=dp[a][i];
    return a;
}
int lca(int a,int b){
    if (ddepth[a]>ddepth[b]) swap(a,b);
    b=jmp(b,ddepth[b]-ddepth[a]);
    if (a==b) return a;
    for (int i=maxlog-1;i>=0;i--){
        if (dp[a][i]!=dp[b][i]){
            a=dp[a][i];
            b=dp[b][i];
        }
    }
    return dp[a][0];
}
 
 //erro ta na dfs ou main;
int main(){
    cin.tie(NULL);cin.sync_with_stdio(false);
    int n,m,k;
    cin>>n>>m>>k;
    for (int i=0;i<n-1;i++){
        int a,b;cin>>a>>b;
        grafo[a].push_back({b,i+1});
        grafo[b].push_back({a,i+1});
    }
    dfs(1,0);
 
    fenwick f(maxn);
    for (int i=1;i<=n;i++) dp[i][0]=pai[i];
    for (int j=1;j<maxlog;j++)for (int i=1;i<=n;i++) dp[i][j]=dp[dp[i][j-1]][j-1];
    while(m--){
        int a;cin>>a;
        
        vector<int>v(a);
        for (int i=0;i<a;i++){
            cin>>v[i];
        }
 
        sort(v.begin(),v.end(), [](int a,int b){ return beg[a]<beg[b];});
        v.push_back(v[0]);
        for (int i=0;i<a;i++){
            int l=lca(v[i],v[i+1]);
 
            f.update(beg[v[i]],1);
            f.update(beg[v[i+1]],1);
            f.update(beg[l],-2);
        }
    }
 
    vector<int> ans;
    for (int i=1;i<=n;i++){
        if (f.query(beg[i],en[i])>=2*k) ans.push_back(volta[i]);
    }
    cout<<ans.size()<<"\n";
    for (auto k1: ans) cout<<k1<<" ";
    cout<<endl;
 
}
#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...