oj.uz

Submission #945286

# Submission time Handle Problem Language Result Execution time Memory
945286 2024-03-13T15:42:39 Z Tuanlinh123 Mergers (JOI19_mergers) C++17
10 / 100
 78 ms 126984 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]);
    bool all=1;
    for (ll i=1; i<n; i++)
        if (col[i]!=col[i+1])
            all=0;
    if (all) {cout << 0; return 0;} 
    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 6 ms 33312 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 4 ms 24924 KB Output is correct
6 Correct 5 ms 33264 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 5 ms 33116 KB Output is correct
9 Correct 5 ms 26968 KB Output is correct
10 Correct 4 ms 22872 KB Output is correct
11 Correct 5 ms 33112 KB Output is correct
12 Correct 5 ms 33204 KB Output is correct
13 Correct 5 ms 26972 KB Output is correct
14 Correct 5 ms 33116 KB Output is correct
15 Correct 5 ms 33116 KB Output is correct
16 Correct 4 ms 24920 KB Output is correct
17 Correct 4 ms 24924 KB Output is correct
18 Correct 5 ms 33116 KB Output is correct
19 Correct 4 ms 24924 KB Output is correct
20 Correct 4 ms 24924 KB Output is correct
21 Correct 5 ms 33116 KB Output is correct
22 Correct 5 ms 33112 KB Output is correct
23 Correct 5 ms 26972 KB Output is correct
24 Correct 4 ms 26968 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 6 ms 33312 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 4 ms 24924 KB Output is correct
6 Correct 5 ms 33264 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 5 ms 33116 KB Output is correct
9 Correct 5 ms 26968 KB Output is correct
10 Correct 4 ms 22872 KB Output is correct
11 Correct 5 ms 33112 KB Output is correct
12 Correct 5 ms 33204 KB Output is correct
13 Correct 5 ms 26972 KB Output is correct
14 Correct 5 ms 33116 KB Output is correct
15 Correct 5 ms 33116 KB Output is correct
16 Correct 4 ms 24920 KB Output is correct
17 Correct 4 ms 24924 KB Output is correct
18 Correct 5 ms 33116 KB Output is correct
19 Correct 4 ms 24924 KB Output is correct
20 Correct 4 ms 24924 KB Output is correct
21 Correct 5 ms 33116 KB Output is correct
22 Correct 5 ms 33112 KB Output is correct
23 Correct 5 ms 26972 KB Output is correct
24 Correct 4 ms 26968 KB Output is correct
25 Correct 5 ms 31068 KB Output is correct
26 Correct 9 ms 45916 KB Output is correct
27 Correct 9 ms 45916 KB Output is correct
28 Correct 8 ms 46168 KB Output is correct
29 Correct 8 ms 45916 KB Output is correct
30 Correct 9 ms 45916 KB Output is correct
31 Correct 6 ms 31068 KB Output is correct
32 Correct 9 ms 46172 KB Output is correct
33 Correct 5 ms 31064 KB Output is correct
34 Correct 8 ms 45916 KB Output is correct
35 Correct 8 ms 45916 KB Output is correct
36 Incorrect 8 ms 45916 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 6 ms 33312 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 4 ms 24924 KB Output is correct
6 Correct 5 ms 33264 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 5 ms 33116 KB Output is correct
9 Correct 5 ms 26968 KB Output is correct
10 Correct 4 ms 22872 KB Output is correct
11 Correct 5 ms 33112 KB Output is correct
12 Correct 5 ms 33204 KB Output is correct
13 Correct 5 ms 26972 KB Output is correct
14 Correct 5 ms 33116 KB Output is correct
15 Correct 5 ms 33116 KB Output is correct
16 Correct 4 ms 24920 KB Output is correct
17 Correct 4 ms 24924 KB Output is correct
18 Correct 5 ms 33116 KB Output is correct
19 Correct 4 ms 24924 KB Output is correct
20 Correct 4 ms 24924 KB Output is correct
21 Correct 5 ms 33116 KB Output is correct
22 Correct 5 ms 33112 KB Output is correct
23 Correct 5 ms 26972 KB Output is correct
24 Correct 4 ms 26968 KB Output is correct
25 Correct 5 ms 31068 KB Output is correct
26 Correct 57 ms 118660 KB Output is correct
27 Correct 76 ms 119136 KB Output is correct
28 Correct 8 ms 45912 KB Output is correct
29 Correct 5 ms 31064 KB Output is correct
30 Correct 5 ms 31068 KB Output is correct
31 Correct 64 ms 119812 KB Output is correct
32 Correct 7 ms 45916 KB Output is correct
33 Correct 64 ms 126984 KB Output is correct
34 Correct 71 ms 118320 KB Output is correct
35 Incorrect 9 ms 45912 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 119740 KB Output is correct
2 Correct 62 ms 121672 KB Output is correct
3 Correct 8 ms 45916 KB Output is correct
4 Correct 8 ms 45916 KB Output is correct
5 Correct 5 ms 31068 KB Output is correct
6 Correct 6 ms 31064 KB Output is correct
7 Correct 8 ms 45916 KB Output is correct
8 Incorrect 78 ms 121552 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 6 ms 33312 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 4 ms 24924 KB Output is correct
6 Correct 5 ms 33264 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 5 ms 33116 KB Output is correct
9 Correct 5 ms 26968 KB Output is correct
10 Correct 4 ms 22872 KB Output is correct
11 Correct 5 ms 33112 KB Output is correct
12 Correct 5 ms 33204 KB Output is correct
13 Correct 5 ms 26972 KB Output is correct
14 Correct 5 ms 33116 KB Output is correct
15 Correct 5 ms 33116 KB Output is correct
16 Correct 4 ms 24920 KB Output is correct
17 Correct 4 ms 24924 KB Output is correct
18 Correct 5 ms 33116 KB Output is correct
19 Correct 4 ms 24924 KB Output is correct
20 Correct 4 ms 24924 KB Output is correct
21 Correct 5 ms 33116 KB Output is correct
22 Correct 5 ms 33112 KB Output is correct
23 Correct 5 ms 26972 KB Output is correct
24 Correct 4 ms 26968 KB Output is correct
25 Correct 5 ms 31068 KB Output is correct
26 Correct 9 ms 45916 KB Output is correct
27 Correct 9 ms 45916 KB Output is correct
28 Correct 8 ms 46168 KB Output is correct
29 Correct 8 ms 45916 KB Output is correct
30 Correct 9 ms 45916 KB Output is correct
31 Correct 6 ms 31068 KB Output is correct
32 Correct 9 ms 46172 KB Output is correct
33 Correct 5 ms 31064 KB Output is correct
34 Correct 8 ms 45916 KB Output is correct
35 Correct 8 ms 45916 KB Output is correct
36 Incorrect 8 ms 45916 KB Output isn't correct
37 Halted 0 ms 0 KB -