제출 #1261427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261427		duccnamm	Mergers (JOI19_mergers)	C++20	100 / 100	312 ms	81932 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
#define ll int
ll n,u,v,f[500005],par[500005],h[500005],k,ans,d[500005];
vector<ll>a[500005],vc[500005];
ll getlab(ll i)
{
    if(f[i]<0)
        return i;
    return f[i]=getlab(f[i]);
}
void connect(ll u,ll v)
{
    u=getlab(u);
    v=getlab(v);
    if(u==v)
        return;
    f[u]+=f[v];
    f[v]=u;
    return;
}
void dfs(ll x,ll pa)
{
    par[x]=pa;
    for(ll it:a[x])
        if(it!=pa)
        {
            h[it]=h[x]+1;
            dfs(it,x);
        }
}
void collab(ll x,ll y)
{
    x=getlab(x);
    y=getlab(y);
    while(x!=y)
    {
        if(h[x]<h[y])
            swap(x,y);
        connect(par[x],x);
        x=getlab(par[x]);
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n-1;i++)
    {
        f[i]=-1;
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    f[n]=-1;
    for(int i=1;i<=n;i++)
    {
        cin>>u;
        vc[u].push_back(i);
    }
    dfs(1,0);
    for(int i=1;i<=k;i++)
        for(int j=1;j<vc[i].size();j++)
            collab(vc[i][0],vc[i][j]);
    for(int i=1;i<=n;i++)
        for(ll it:a[i])
            if(getlab(i)!=getlab(it))
                d[getlab(i)]++;
    for(int i=1;i<=n;i++)
        if(d[i]==1)
            ans++;
    cout<<(ans+1)/2;
}

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