제출 #949199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
949199		Tuanlinh123	Mergers (JOI19_mergers)	C++17	70 / 100	695 ms	250540 KiB

mergers

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
 
const ll maxn=500005;
pll sp[20][maxn];
vector <pll> euler;
vector <ll> leaf, A[maxn];
ll P[maxn], col[maxn], lca[maxn], pa[maxn], dsu[maxn];
 
void dfs(ll u)
{
    lca[u]=sz(euler)+1, euler.pb({lca[u], u});
    for (ll v:A[u])
        if (v!=pa[u])
            pa[v]=u, dfs(v), euler.pb({lca[u], u});
    if (sz(A[u])==1) leaf.pb(u);
}
 
void initlca()
{
    ll n=sz(euler);
    for (ll i=0; i<n; i++)
        sp[0][i+1]=euler[i];
    for (ll i=1; i<20; i++)
        for (ll j=1; j+(1<<i)<=n+1; j++)
            sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
}
 
ll LCA(ll u, ll v)
{
    if (!u || !v) return u+v;
    ll l=lca[u], r=lca[v];
    if (l>r) swap(l, r);
    ll j=__lg(r-l+1);
    return min(sp[j][l], sp[j][r-(1<<j)+1]).se;
}
 
ll Find(ll i)
{
    if (dsu[i]<0) return i;
    return dsu[i]=Find(dsu[i]);
}
 
void Union(ll a, ll b)
{
    a=Find(a), b=Find(b);
    if (a==b) return;
    if (dsu[a]>dsu[b]) swap(a, b);
    P[a]=LCA(P[a], P[b]), dsu[a]+=dsu[b], dsu[b]=a;
}

void dfs1(ll u)
{
    for (ll v:A[u])
        if (v!=pa[u])
            dfs1(v), P[col[u]]=LCA(P[col[u]], P[col[v]]);
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, k; cin >> n >> k;
    for (ll i=1; i<n; i++)
    {
        ll u, v; cin >> u >> v;
        A[u].pb(v), A[v].pb(u);
    }
    dfs(1), initlca();
    for (ll i=1; i<=n; i++)
        cin >> col[i], P[col[i]]=LCA(P[col[i]], i), dsu[i]=-1;
    dfs1(1);
    for (ll i=1; i<=n; i++)
        if (i!=P[col[i]])
            Union(col[i], col[pa[i]]);
    for (ll i=1; i<=n; i++) col[i]=Find(col[i]);
    for (ll i=1; i<=k; i++) P[i]=0;
    for (ll i=1; i<=n; i++)
        for (ll j:A[i])
            if (col[i]!=col[j])
            {
                if (P[col[i]]==0) P[col[i]]=col[j];
                else if (P[col[i]]!=col[j]) P[col[i]]=-1;
            }
    ll cnt=0;
    for (ll i=1; i<=k; i++)
        cnt+=P[i]>0;
    cout << (cnt+1)/2;
 
}

컴파일 시 표준 에러 (stderr) 메시지

mergers.cpp: In function 'void initlca()':
mergers.cpp:34:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   34 |             sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
      |                                                    ~^~

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