Submission #887077

#	Time	Username	Problem	Language	Result	Execution time	Memory
887077		maxFedorchuk	Mergers (JOI19_mergers)	C++14	100 / 100	2062 ms	217816 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 prfsum[MX],ans=0;
 
long long DFS2(long long zar,long long mun)
{
    long long z=0;
 
    for(auto u:mas[zar])
    {
        if(u!=mun)
        {
            z+=DFS2(u,zar);
            prfsum[zar]+=prfsum[u];
        }
    }
 
    if(zar==1)
    {
        ans+=(z==1);
    }
    else
    {
        if(prfsum[zar]==0)
        {
            ans+=(z==0);
            z=1;
        }
    }
 
 
 
    return z;
}
 
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);
    }
 
  	tin[0]=0;
    DFSCNT(1,0);
  	timer++;
  	tou[0]=timer;
 
    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<<(ans+1)/2<<"\n";
    return 0;
}

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