oj.uz

Submission #949200

# Submission time Handle Problem Language Result Execution time Memory
949200 2024-03-19T03:40:35 Z Tuanlinh123 Mergers (JOI19_mergers) C++17
10 / 100
 89 ms 130236 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 dfs1(ll u)
{
    for (ll v:A[u])
        if (v!=pa[u])
            dfs1(v), P[col[u]]=LCA(P[col[u]], P[col[v]]);
}

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;
    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 l:leaf) P[col[l]]=0;
    ll root=0;
    for (ll i=1; i<=n; i++)
        if (P[col[i]])
        {
            root=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]] && (root || col[l]!=col[1]))
            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 5 ms 24924 KB Output is correct
2 Correct 7 ms 33116 KB Output is correct
3 Correct 6 ms 33300 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 5 ms 25008 KB Output is correct
6 Correct 6 ms 33116 KB Output is correct
7 Correct 5 ms 20828 KB Output is correct
8 Correct 6 ms 33116 KB Output is correct
9 Correct 5 ms 26972 KB Output is correct
10 Correct 5 ms 22876 KB Output is correct
11 Correct 5 ms 33116 KB Output is correct
12 Correct 5 ms 33116 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 24924 KB Output is correct
17 Correct 5 ms 24924 KB Output is correct
18 Correct 6 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 6 ms 33116 KB Output is correct
23 Correct 5 ms 26968 KB Output is correct
24 Correct 5 ms 26972 KB Output is correct

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 6 ms 33300 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 5 ms 25008 KB Output is correct
6 Correct 6 ms 33116 KB Output is correct
7 Correct 5 ms 20828 KB Output is correct
8 Correct 6 ms 33116 KB Output is correct
9 Correct 5 ms 26972 KB Output is correct
10 Correct 5 ms 22876 KB Output is correct
11 Correct 5 ms 33116 KB Output is correct
12 Correct 5 ms 33116 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 24924 KB Output is correct
17 Correct 5 ms 24924 KB Output is correct
18 Correct 6 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 6 ms 33116 KB Output is correct
23 Correct 5 ms 26968 KB Output is correct
24 Correct 5 ms 26972 KB Output is correct
25 Correct 5 ms 31068 KB Output is correct
26 Correct 8 ms 45996 KB Output is correct
27 Correct 8 ms 45916 KB Output is correct
28 Correct 8 ms 46168 KB Output is correct
29 Correct 10 ms 45916 KB Output is correct
30 Correct 8 ms 46168 KB Output is correct
31 Correct 6 ms 31068 KB Output is correct
32 Correct 8 ms 46172 KB Output is correct
33 Correct 5 ms 31320 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 5 ms 24924 KB Output is correct
2 Correct 7 ms 33116 KB Output is correct
3 Correct 6 ms 33300 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 5 ms 25008 KB Output is correct
6 Correct 6 ms 33116 KB Output is correct
7 Correct 5 ms 20828 KB Output is correct
8 Correct 6 ms 33116 KB Output is correct
9 Correct 5 ms 26972 KB Output is correct
10 Correct 5 ms 22876 KB Output is correct
11 Correct 5 ms 33116 KB Output is correct
12 Correct 5 ms 33116 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 24924 KB Output is correct
17 Correct 5 ms 24924 KB Output is correct
18 Correct 6 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 6 ms 33116 KB Output is correct
23 Correct 5 ms 26968 KB Output is correct
24 Correct 5 ms 26972 KB Output is correct
25 Correct 6 ms 31064 KB Output is correct
26 Correct 64 ms 123268 KB Output is correct
27 Correct 75 ms 121596 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 71 ms 122048 KB Output is correct
32 Correct 8 ms 45916 KB Output is correct
33 Correct 78 ms 130236 KB Output is correct
34 Correct 71 ms 122296 KB Output is correct
35 Incorrect 8 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 55 ms 122548 KB Output is correct
2 Correct 63 ms 123848 KB Output is correct
3 Correct 10 ms 45916 KB Output is correct
4 Correct 8 ms 45916 KB Output is correct
5 Correct 5 ms 31064 KB Output is correct
6 Correct 6 ms 31068 KB Output is correct
7 Correct 8 ms 45916 KB Output is correct
8 Correct 89 ms 121816 KB Output is correct
9 Incorrect 8 ms 45864 KB Output isn't correct
10 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 6 ms 33300 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 5 ms 25008 KB Output is correct
6 Correct 6 ms 33116 KB Output is correct
7 Correct 5 ms 20828 KB Output is correct
8 Correct 6 ms 33116 KB Output is correct
9 Correct 5 ms 26972 KB Output is correct
10 Correct 5 ms 22876 KB Output is correct
11 Correct 5 ms 33116 KB Output is correct
12 Correct 5 ms 33116 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 24924 KB Output is correct
17 Correct 5 ms 24924 KB Output is correct
18 Correct 6 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 6 ms 33116 KB Output is correct
23 Correct 5 ms 26968 KB Output is correct
24 Correct 5 ms 26972 KB Output is correct
25 Correct 5 ms 31068 KB Output is correct
26 Correct 8 ms 45996 KB Output is correct
27 Correct 8 ms 45916 KB Output is correct
28 Correct 8 ms 46168 KB Output is correct
29 Correct 10 ms 45916 KB Output is correct
30 Correct 8 ms 46168 KB Output is correct
31 Correct 6 ms 31068 KB Output is correct
32 Correct 8 ms 46172 KB Output is correct
33 Correct 5 ms 31320 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 -