Submission #884813

#	Time	Username	Problem	Language	Result	Execution time	Memory
884813		maxFedorchuk	Railway (BOI17_railway)	C++14	100 / 100	337 ms	59192 KiB

railway

#include <bits/stdc++.h>
using namespace std;

const long long MX=1e5+10;
const long long lg=30;

vector < long long > mas[MX];

long long prd[lg][MX];

long long tin[MX];
long long tou[MX];

long long timer=0;

void DFSCNT(long long zar,long long mun)
{
    timer++;
    tin[zar]=timer;

    prd[0][zar]=mun;

    for(long long i=1;i<lg;i++)
    {
        prd[i][zar]=prd[i-1][prd[i-1][zar]];
    }

    for(auto u:mas[zar])
    {
        if(u!=mun)
        {
            DFSCNT(u,zar);
        }
    }

    timer++;
    tou[zar]=timer;

    return;
}

long long chkprd(long long pr,long long son)
{
    return ((tin[pr]<=tin[son]) && (tou[son]<=tou[pr]));
}

long long lca(long long a,long long b)
{
    if(chkprd(a,b))
    {
        return a;
    }

    if(chkprd(b,a))
    {
        return b;
    }

    for(long long i=lg-1;i>=0;i--)
    {
        if(!chkprd(prd[i][a],b))
        {
            a=prd[i][a];
        }
    }

    return prd[0][a];
}

bool cmp(long long a,long long b)
{
    return (tin[a]<tin[b]);
}

vector < pair < long long , long long > > ans;
vector < long long > vis(MX);

long long n,q,k;

void DFS2(long long zar,long long mun)
{
    for(auto u:mas[zar])
    {
        if(u!=mun)
        {
            DFS2(u,zar);
            vis[zar]+=vis[u];
        }
    }

    if(vis[zar]>=k)
    {
        ans.push_back({zar,prd[0][zar]});
    }

    return;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    map < pair < long long , long long > , long long > rb;

    cin>>n>>q>>k;

    long long a,b;
    for(long long i=1;i<n;i++)
    {
        cin>>a>>b;
        mas[a].push_back(b);
        mas[b].push_back(a);

        rb[{a,b}]=i;
        rb[{b,a}]=i;
    }

    tin[0]=timer;

    DFSCNT(1,0);

    timer++;
    tou[0]=timer;

    while(q--)
    {
        vector < long long > vc;

        long long sz;
        cin>>sz;

        for(long long i=0;i<sz;i++)
        {
            cin>>a;
            vc.push_back(a);
        }

        sort(vc.begin(),vc.end(),cmp);

        for(long long i=0;i<sz;i++)
        {
            vis[vc[i]]++;
            vis[lca(vc[i],vc[(i+1)%sz])]--;
        }
    }

    DFS2(1,0);

    vector < long long > res;
    for(auto u:ans)
    {
        res.push_back(rb[u]);
    }
    sort(res.begin(),res.end());

    cout<<res.size()<<"\n";
    for(auto u:res)
    {
        cout<<u<<" ";
    }
    cout<<"\n";

    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