Submission #932090

#	Time	Username	Problem	Language	Result	Execution time	Memory
932090		irmuun	Railway (BOI17_railway)	C++17	23 / 100	1083 ms	21308 KiB

railway

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll int
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    vector<int>adj[n+5];
    vector<pair<int,int>>edge;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        edge.pb({u,v});
        adj[u].pb(v);
        adj[v].pb(u);
    }
    int s[m+5];
    vector<int>need[m+5];
    for(int i=1;i<=m;i++){
        cin>>s[i];
        need[i].resize(s[i]);
        for(int j=0;j<s[i];j++){
            cin>>need[i][j];
        }
    }
    vector<int>par(n+5);
    vector<int>f(n+5),e(n+5);
    int cur=0;
    function <void(int,int)> dfs=[&](int x,int p){
        f[x]=cur++;
        par[x]=p;
        for(auto y:adj[x]){
            if(y!=p){
                dfs(y,x);
            }
        }
        e[x]=cur++;
    };
    vector<int>cnt(n+5,0),a(n+5,0);
    function <void(int,int)> dfs1=[&](int x,int p){
        cnt[x]=a[x];
        for(auto y:adj[x]){
            if(y!=p){
                dfs1(y,x);
                cnt[x]+=cnt[y];
            }
        }
    };
    dfs(1,0);
    cur=0;
    vector<int>ans,choose(n+5,0);
    for(int j=1;j<=m;j++){
        fill(all(a),0);
        for(auto i:need[j]){
            a[i]=1;
        }
        dfs1(1,0);
        for(int i=0;i<n;i++){
            auto [x,y]=edge[i];
            if(par[y]==x) swap(x,y);
            if(0<cnt[x]&&cnt[x]<s[j]){
                choose[i+1]++;
            }
        }
    }
    for(int i=1;i<n;i++){
        if(choose[i]>=k){
            ans.pb(i);
        }
    }
    cout<<ans.size()<<"\n";
    for(auto i:ans){
        cout<<i<<' ';
    }
}

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