제출 #1239176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239176		lambd47	Railway (BOI17_railway)	C++20	100 / 100	60 ms	20928 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int lg=20;
const int MX=1e5+7;
int dp[lg][MX];
void solve() {
    int n,m,k;cin>>n>>m>>k;
    vector<int> tin(n);
    vector<int> val(n,0);
    vector<int> resp(n,0);
    vector<int> dep(n,0);
    vector<int> edpai(n,-1);
    vector<int> edgs(n);
    vector<vector<int>> adj(n);
    L(i,0,n-2){
        int a,b;cin>>a>>b;a--;b--;
        adj[a].push_back(i);
        adj[b].push_back(i);
        edgs[i]=a^b;
    }
    int tmp=0;
    edpai[0]=n-1;
    auto dfs=[&](auto&& self, int node,int p)->void{
        tin[node]=tmp++;
        dp[0][node]=p;
        dep[node]=dep[p]+1;
        L(i,1,lg-1){
            dp[i][node]=dp[i-1][dp[i-1][node]];
        }
        for(auto e:adj[node]){
            int a=edgs[e]^node;
            if(a==p)continue;
            edpai[a]=e;
            self(self,a,node);
        }
    };
    dfs(dfs,0,0);

    auto lca=[&](int a, int b)->int{
        if(dep[a]<dep[b])swap(a,b);
        int d=dep[a]-dep[b];
        L(i,0,lg-1){
            if(d&(1<<i))a=dp[i][a];
        }
        if(a==b)return a;
        R(i,lg-1,0){
            if(dp[i][a]!=dp[i][b]){
                a=dp[i][a];
                b=dp[i][b];
            }
        }
        return dp[0][a];
    };


        
    auto solv=[&](vector<int>& vec){
        for(auto a:vec)val[a]++;
        sort(vec.begin(),vec.end(),[&](int a, int b){
                return tin[a]<tin[b];
        });
        int lcgoat=vec[0];
        L(i,1,sz(vec)-1){
            int at=lca(vec[i],vec[i-1]);
            val[at]--;
            lcgoat=lca(at,lcgoat);
        }
        val[lcgoat]--;
    };

    L(i,0,m-1){
        int k;cin>>k;
        vector<int> aux(k);
        L(i,0,k-1){
            cin>>aux[i];aux[i]--;
        }
        solv(aux);
    }


    auto dfsfind=[&](auto&& self, int node, int pai)->int{
        resp[edpai[node]]=val[node];
        for(auto e:adj[node]){
            int a=edgs[e]^node;
            if(a==pai)continue;
            resp[edpai[node]]+=self(self,a,node);
        }
        return resp[edpai[node]];
    };
    dfsfind(dfsfind, 0,0);
    vector<int> fina;
    L(i,0,n-2){
        if(resp[i]>=k)fina.push_back(i+1);
    }
    cout<<sz(fina)<<"\n";
    for(auto a:fina)cout<<a<<" ";



}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	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