Submission #932088

#	Time	Username	Problem	Language	Result	Execution time	Memory
932088		irmuun	Railway (BOI17_railway)	C++17	8 / 100	1091 ms	22224 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++;
    };
    dfs(1,0);
    cur=0;
    vector<int>ans,cnt(n+5,0);
    for(auto [x,p]:edge){
        cur++;
        if(par[p]==x) swap(x,p);
        int c=0;
        for(int j=1;j<=m;j++){
            c=0;
            for(auto r:need[j]){
                if(f[x]<=f[r]&&e[r]<=e[x]){
                    c++;
                }
            }
            if(0<c&&c<s[j]){
                cnt[cur]++;
            }
        }
    }
    for(int i=1;i<n;i++){
        if(cnt[i]>=k){
            ans.pb(i);
        }
    }
    cout<<ans.size()<<"\n";
    for(auto i:ans){
        cout<<i<<' ';
    }
}

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