oj.uz

Submission #945270

# Submission time Handle Problem Language Result Execution time Memory
945270 2024-03-13T15:34:39 Z Tuanlinh123 Mergers (JOI19_mergers) C++17
0 / 100
 57 ms 115388 KB 
#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 dfs2(ll u)
{
    for (ll v:A[u])
        if (v!=pa[u])
            pa[v]=u, dfs2(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;
    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 l:leaf) P[col[l]]=0;
    for (ll i=1; i<=n; i++)
        if (P[col[i]])
        {
            pa[i]=0, dfs2(i);
            break;
        }
    for (ll i=1; i<=n; i++)
        P[col[i]]=1;
    for (ll i=1; i<=n; i++)
        for (ll j:A[i])
            if (j!=pa[i] && col[i]!=col[j])
                P[col[i]]=0;
    ll cnt=0;
    for (ll l:leaf)
        if (P[col[l]])
            cnt++, P[col[l]]=0;
    cout << (cnt+1)/2;
}

Compilation message

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 7 ms 33116 KB Output is correct
3 Correct 7 ms 33116 KB Output is correct
4 Correct 6 ms 26972 KB Output is correct
5 Incorrect 6 ms 25084 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 7 ms 33116 KB Output is correct
3 Correct 7 ms 33116 KB Output is correct
4 Correct 6 ms 26972 KB Output is correct
5 Incorrect 6 ms 25084 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 7 ms 33116 KB Output is correct
3 Correct 7 ms 33116 KB Output is correct
4 Correct 6 ms 26972 KB Output is correct
5 Incorrect 6 ms 25084 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 115388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 7 ms 33116 KB Output is correct
3 Correct 7 ms 33116 KB Output is correct
4 Correct 6 ms 26972 KB Output is correct
5 Incorrect 6 ms 25084 KB Output isn't correct
6 Halted 0 ms 0 KB -