제출 #1318940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318940		wangzhiyi33	Railway (BOI17_railway)	C++20	100 / 100	195 ms	46940 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back
const int maxn=1e5;

vector<ii>adj[maxn+2];
int n,m,k,sz[maxn+2];
vector<int>isi[maxn+2],ans;
map<int,int>freq[maxn+2];
int slh[maxn+2];

void dfs(int cur,int par,int edge){
    for(auto [x,id] : adj[cur]){
        if(x==par)continue;
        dfs(x,cur,id);

        if(freq[x].size()>freq[cur].size()){
            swap(freq[x],freq[cur]);
            swap(slh[x],slh[cur]);
        }

        for(auto y : freq[x]){
            freq[cur][y.fir]+=y.sec;
            if(freq[cur][y.fir]==sz[y.fir]){
                slh[cur]++;
            }
        }
    }

    for(auto x : isi[cur]){
        freq[cur][x]++;
        if(freq[cur][x]==sz[x]){
            slh[cur]++;
        }
    }

    if(freq[cur].size()-slh[cur]>=k){
        ans.pb(edge);
    }
}

signed main(){
    cin>>n>>m>>k;
    for(int q=1;q<n;q++){
        int u,v;
        cin>>u>>v;
        adj[u].pb({v,q});
        adj[v].pb({u,q});
    }
    for(int q=1;q<=m;q++){
        cin>>sz[q];
        for(int w=1;w<=sz[q];w++){
            int x; cin>>x;
            isi[x].pb(q);
        }
    }
    dfs(1,0,0);

    sort(ans.begin(),ans.end());
    cout<<ans.size()<<endl;
    for(auto x : ans){
        cout<<x<<' ';
    }
    cout<<endl;
}

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