Submission #1135421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135421		LeonidCuk	Railway (BOI17_railway)	C++20	100 / 100	362 ms	67028 KiB

railway

#include <bits/stdc++.h>
using namespace std;
vector<int>g[100000],lca[100000],d(100000),koj[100000],koj2[100000],ans(100000);
int ans1=0;
set<int>s[100000];
map<pair<int,int>,int>ma;
void dfs1(int a,int b,int dep)
{
    lca[a].push_back(b);
    d[a]=dep;
    for(int i=1;i<20;i++)
    {
        lca[a].push_back(lca[lca[a][i-1]][i-1]);
    }
    for(auto i:g[a])
    {
        if(i!=b)
        {
            dfs1(i,a,dep+1);
        }
    }
}
void dfs2(int a,int b,int k)
{
    for(auto i:g[a])
    {
        if(i!=b)
        {
            dfs2(i,a,k);
            if(s[i].size()>=k)
            {
                ans[ma[{a,i}]]=1;
                ans1++;
            }
            if(s[i].size()>s[a].size())swap(s[i],s[a]);
        }
    }
    for(auto i:g[a])
    {
        if(i!=b)
        {
            for(auto it=s[i].begin();it!=s[i].end();it++)
            {
                s[a].insert(*it);
            }
        }
    }
    for(auto i:koj[a])
    {
        s[a].insert(i);
    }
    for(auto i:koj2[a])
    {
        s[a].erase(i);
    }
}
int findlca(int a,int b)
{
    if(d[a]<d[b])swap(a,b);
    for(int i=19;i>=0;i--)
    {
        if(d[lca[a][i]]>=d[b])a=lca[a][i];
    }
    if(a==b)return a;
    for(int i=19;i>=0;i--)
    {
        if(lca[a][i]!=lca[b][i])
        {
            a=lca[a][i];
            b=lca[b][i];
        }
    }
    return lca[a][0];
}
int main()
{
    int n,m,k,a,b,n1;
    cin>>n>>m>>k;
    for(int i=0;i<n-1;i++)
    {
        cin>>a>>b;
        g[a-1].push_back(b-1);
        g[b-1].push_back(a-1);
        ma[{a-1,b-1}]=i;
        ma[{b-1,a-1}]=i;
    }
    dfs1(0,0,0);
    for(int i=0;i<m;i++)
    {
        cin>>n1;
        int res=-1;
        for(int j=0;j<n1;j++)
        {
            cin>>a;a--;
            koj[a].push_back(i);
            if(res==-1)res=a;
            else res=findlca(res,a);
        }
        koj2[res].push_back(i);
    }
    dfs2(0,0,k);
    cout<<ans1<<endl;
    for(int i=0;i<n;i++)
    {
        if(ans[i]==1)cout<<i+1<<" ";
    }
    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