제출 #1130279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130279		I_FloPPed21	Railway (BOI17_railway)	C++20	100 / 100	105 ms	25020 KiB

railway

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=2e5+1;
int n,m,k;
vector<int>adj[N];
int binlift[N][21],timp=0,in[N],out[N],where[N],height[N];
void dfs(int nod,int p)
{
    binlift[nod][0]=p;
    timp++;
    height[nod]=height[p]+1;
    in[nod]=timp;
    for(int i=1; i<=20; i++)
    {
        binlift[nod][i]=binlift[binlift[nod][i-1]][i-1];
    }
    for(auto u:adj[nod])
    {
        if(u!=p)
        {
            dfs(u,nod);
        }
    }
    out[nod]=timp;
}
int get_lca(int a,int b)
{
    if(height[a]<height[b])
        swap(a,b);


    if(in[b]<=in[a]&&out[a]<=out[b])
    {
        return b;
    }
    for(int i=20; i>=0; i--)
    {
        if(height[binlift[a][i]]>=height[b])
            a=binlift[a][i];
    }
    for(int i=20; i>=0; i--)
    {
        if(binlift[a][i]!=binlift[b][i])
        {
            a=binlift[a][i];
            b=binlift[b][i];
        }
    }
    return binlift[a][0];
}
vector<pair<int,int>>muchii;
int aib[N];
void update(int poz,int val)
{
    for(int i=poz; i<=n; i+=(i&-i))
    {
        aib[i]+=val;
    }
}
int query(int poz)
{
    int ans=0;
    for(int i=poz; i>0; i-=(i&-i))
    {
        ans+=aib[i];
    }
    return ans;
}
void citeste()
{
    cin>>n>>m>>k;
    for(int i=1; i<n; i++)
    {
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        muchii.push_back({a,b});
    }
}
void rezolva()
{
    for(int i=1; i<=m; i++)
    {
        int siz;
        cin>>siz;
        vector<int>d(siz+3);
        for(int i=1; i<=siz; i++)
        {
            cin>>d[i];
        }
        sort(d.begin()+1,d.begin()+siz+1,[](int x,int y)
        {
            return in[x]<in[y];
        });
        d[siz+1]=d[1];
        for(int i=1; i<=siz; i++)
        {
            int lca=get_lca(d[i],d[i+1]);
            update(in[d[i]],1);
            update(in[d[i+1]],1);
            update(in[lca],-2);
        }
    }

    vector<int>ans;
    int cnt=0;
    for(auto [x,y]:muchii)
    {
        cnt++;
        if(binlift[y][0]==x)
            swap(x,y);
        if(query(out[x])-query(in[x]-1)>=2*k)
        {
            ans.push_back(cnt);
        }
    }
    cout<<ans.size()<<'\n';
    for(auto u:ans)
        cout<<u<<" ";
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    citeste();
    dfs(1,0);
    rezolva();

    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