Submission #410818

#	Time	Username	Problem	Language	Result	Execution time	Memory
410818		Malheiros	Railway (BOI17_railway)	C++17	36 / 100	107 ms	23260 KiB

railway

#include <bits/stdc++.h>
 
using namespace std;
#define ll long long

const int maxn=1e5+10;
const int maxlog=20;

struct fenwick{

    int* bit;
    int size;
    int n;
    fenwick(int n1,int gambjohn){
        bit= new int[n1+1];
        for (int i=0;i<=n;i++) bit[i]=0;
        size=n1;
        n=gambjohn;
    }
    
    void update(int pos, int val) {
	for (; pos <= n; pos += pos & (-pos)) bit[pos] += val;
}

int query(int a, int b) {
	int ans = 0;
	for (; b; b -= b & (-b)) ans += bit[b];
	for (a--; a; a -= a & (-a)) ans -= bit[a];
	return ans;
}

};

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,n);
    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;

}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:16:38: warning: 'f.fenwick::n' may be used uninitialized in this function [-Wmaybe-uninitialized]
   16 |         for (int i=0;i<=n;i++) bit[i]=0;
      |                                ~~~~~~^~
railway.cpp:83:13: note: 'f.fenwick::n' was declared here
   83 |     fenwick f(maxn,n);
      |             ^

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