oj.uz

Submission #949234

# Submission time Handle Problem Language Result Execution time Memory
949234 2024-03-19T04:02:49 Z Tuanlinh123 Mergers (JOI19_mergers) C++17
0 / 100
 59 ms 127672 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], cnt[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), cnt[u]+=cnt[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++)
        cnt[i]++, cnt[P[col[i]]]--;
    dfs1(1);
    for (ll i=1; i<=n; i++)
        if (pa[i] && cnt[i])
            Union(i, pa[i]);
    for (ll i=1; i<=k; i++) P[i]=0;
    for (ll i=1; i<=n; i++)
        if (!cnt[i] && pa[i])
            P[Find(i)]++, P[Find(pa[i])]++;
    ll cnt=0;
    for (ll i=1; i<=n; i++)
        cnt+=P[i]==1;
    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 26972 KB Output is correct
2 Correct 6 ms 35164 KB Output is correct
3 Incorrect 6 ms 35164 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 126904 KB Output is correct
2 Correct 57 ms 127672 KB Output is correct
3 Incorrect 9 ms 47964 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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