Submission #410807

#	Time	Username	Problem	Language	Result	Execution time	Memory
410807		Malheiros	Railway (BOI17_railway)	C++17	36 / 100	125 ms	25696 KiB

railway

#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];
}

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=2;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;

}

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