제출 #1260673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260673		Top1BUCODE	Railway (BOI17_railway)	C++17	100 / 100	119 ms	44740 KiB

railway

#include <bits/stdc++.h>
using namespace std;
// https://trap.jp/post/1224/
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s)))
#define fi first
#define se second
#define upb
#define lwb
#define ll long long
#define twt int t;cin>>t;while (t--)
#define si set<int>
#define mi2 map<int,int>
#define i2 pair<int,int>
#define li pair<ll,int>
#define il pair<int,ll>
#define l2 pair<ll,ll>
#define pb push_back
int n,m,k,h[100003],sp[100003][19],c[100003];
set<int> b[100003];
vector<i2> a[100003];
vector<int> ans,del[100003];
void pre_dfs(int u,int p){
    for (i2 v:a[u]){
        if (v.se==p) continue;
        sp[v.se][0]=u;
        h[v.se]=h[u]+1;
        pre_dfs(v.se,u);
    }
}
int lca(int u,int v){
    if (h[u]<h[v]) swap(u,v);
    int x=h[u]-h[v];
    for (int i=17;i>=0;i--) if (x>>i&1) u=sp[u][i];
    if (u==v) return u;
    for (int i=17;i>=0;i--)
    if (sp[u][i]!=sp[v][i]){
        u=sp[u][i];
        v=sp[v][i];
    }
    return sp[u][0];
}
void dfs(int u,int p,int cs){
    for (i2 v:a[u]){
        if (v.se==p) continue;
        dfs(v.se,u,v.fi);
        if (b[v.se].size()>b[u].size()) {
            swap(b[v.se],b[u]);
        }
        for (int x:b[v.se]) b[u].insert(x);
        b[v.se].clear();
    }
//    cout<<u<<": ";
//    for (int x:b[u]) cout<<x<<" ";
//    cout<<"\n";
    for (int x:del[u]) {
        if (b[u].find(x)!=b[u].end()) b[u].erase(b[u].find(x));
    }
//    cout<<u<<": ";
//    for (int x:b[u]) cout<<x<<" ";
//    cout<<"\n";
    if (p!=0){
        if (b[u].size()>=k) ans.push_back(cs);
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//    freopen("TREE.inp","r",stdin);
    cin>>n>>m>>k;
    for (int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        a[u].push_back({i,v});
        a[v].push_back({i,u});
    }
    pre_dfs(1,0);
    for (int j=1;j<=log2(n);j++)
        for (int i=1;i<=n;i++)
            sp[i][j]=sp[sp[i][j-1]][j-1];
    for (int i=1;i<=m;i++){
        int len;
        cin>>len;
        for (int j=1;j<=len;j++) cin>>c[j];
        int acs=0;
        for (int j=1;j<=len;j++)
            if (acs!=0) acs=lca(acs,c[j]);
            else acs=c[j];
        for (int j=1;j<=len;j++){
//            cout<<c[j]<<" "<<acs<<"\n";
            b[c[j]].insert(i);
            del[acs].push_back(i);
        }
//        cout<<i<<" "<<acs<<"\n";
    }
    dfs(1,0,0);
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<"\n";
    for (int x:ans) cout<<x<<" ";
    return 0;
}

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