Submission #886315

#	Time	Username	Problem	Language	Result	Execution time	Memory
886315		maxFedorchuk	Mergers (JOI19_mergers)	C++14	0 / 100	93 ms	127504 KiB

mergers

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

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

vector < long long > mas[MX];
long long prd[lg][MX];

long long tin[MX],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 ch_prd(long long pr,long long sn)
{
    return (tin[pr]<=tin[sn] && tou[sn]<=tou[pr]);
}

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

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

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

    return a;
}

vector < long long > com[MX];

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

long long maslus[MX];
long long prfsum[MX];

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

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

    if(zar==1)
    {
        return;
    }

    if(maslus[zar]==0 && prfsum[zar]==0)
    {
        maslus[zar]++;
    }

    return;
}

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

    long long n,k;
    cin>>n>>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);
    }

    DFSCNT(1,0);

    for(long long i=1;i<=n;i++)
    {
        cin>>a;
        com[a].push_back(i);
    }

    for(long long i=1;i<=k;i++)
    {
        sort(com[i].begin(),com[i].end(),cmp);

        long long sz=com[i].size();
        for(long long j=0;j<sz;j++)
        {
            prfsum[com[i][j]]++;
            prfsum[lca(com[i][j],com[i][(j+1)%sz])]--;
        }
    }

    DFS2(1,0);

    cout<<maslus[1]<<"\n";
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30